HDU 2521 反素數（分解質因數）

思路：

其實跟反素數沒有什麼關系，就是讓你求區間裡的數的因數的個數最多的那個值，如果有多個符合，取最小。

分解質因數，比如24可以分解為： 23∗31 是以24的所有因數的個數就是（3+1）*（1+1） = 8

仔細考慮一下，每個質因子的幂指數都可以選擇 [0,x]

反素數

定義：

對于任何正整數x,其約數的個數記做g(x).例如g(1)=1,g(6)=4.如果某個正整數x滿足：對于任意 i(0<i<x) 都有 g(i)<g(x) 則稱x為反素數

兩條性質：

1，一個反素數的所有質因子必然是從2開始的連續若幹個質數，因為反素數是保證約數個數為的這個數盡量小。

（證明：反證法，n為反素數，如果不是從2開始的連續若幹個質數的話，假設缺x，把其中比x大的某個質因子換成x，設這個新數為m，是以g（m）= g（n），相悖。）

2， p=2t1∗3t2∗5t3∗7t4..... 必然 t1>=t2>=t3>=....

(證明：反證法，如果某 tx<ty(x<y) 那麼将tx和ty換個位置就能得到和這個數的因子的數量相等的，比這個數小的一個數，相悖。）

AC代碼：

#include <iostream>
#include <cstdio>

using namespace std;

int a[];

int main()
{
    //freopen("output.txt","w",stdout);
    int t;
    int l,r;
    int ans;
    int temp,m;

    a[] = ;
    for(int i = ;i <= ;i++){
        int now = i;
        int nn = ;
        temp = ;
        for(int j = ;j <= now;j++){
            if(now % j == ){
                nn++;
                now /= j;
                while(now % j == ){
                    nn++;
                    now /= j;
                }
                temp *= (nn+);
                nn = ;
            }
        }
        a[i] = temp;
    }

    scanf("%d",&t);
    while(t--){
        scanf("%d%d",&l,&r);
        m = a[l];
        ans = l;
        for(int i = l+;i <= r;i++){
            if(a[i]>m){
                m = a[i];
                ans = i;
            }
        }
        printf("%d\n",ans);
    }

    return ;
}