URAL 1748

題目大意：找出T組不大於ni（i=1,2,3,...,T）的因子數最多的數mi(i=1,2,3,...,T)，有多個數時輸出最小的。

Time Limit:1000MS     Memory Limit:65536KB     64bit IO Format:%I64d & %I64u

數據規模：1<=T=100,1<=ni(i=1,2,3,...,T)<=10^18。

理論基礎：定理：如果:m=p1^k1*p2^k2*...那麼：m的因子數=(k1+1)*(k2+1)*...。

題目分析：由定理可以知道，我們如果：(p1<p2<p3<...)且（k1>=k2>=k3>=...）且m不超過n，則m即為所求的解。

可知解為m不超過ns時素因子個數最多的情況下，小素數的指數盡可能多的情況，且達到最多素數時，假設，已知所有的素數的積為m，則問題轉化為子結構：不超過n/m的情況下，求一個因子最多的最小數問題。這個我們直接深搜就可以了。

代碼如下:

#include<iostream>   
#include<cstdio>   
using namespace std;  
typedef long long LL;  
typedef long long unsigned LU;  
LU n,num,cnt;  
int T,p[17]={0,2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,51};  
void dfs(LU now,int dep,LU pdt,int bor)  
{  
    LU i;  
    int j,pdtt,t;  
    if(dep==16)return;  
    if(pdt>cnt||(pdt==cnt&&now<num))  
    {  
        num=now;  
        cnt=pdt;  
    }  
    j=0,t=1,i=now;  
    while(j<bor)  
    {  
        j++;  
        t++;  
        if(n/i<p[dep])break;  
        pdtt=pdt*t;  
        if(i<=n/p[dep])  
        {  
            i=i*p[dep];  
            dfs(i,dep+1,pdtt,j);  
        }  
        else break;  
    }  
}  
  
int main()  
{  
    scanf("%d",&T);  
    while(T--)  
    {  
        scanf("%I64u",&n);  
        if(n==1)  
        {  
            printf("1 1\n");  
            continue;  
        }  
        num=1,cnt=1;  
        dfs(1,1,1,60);  
        printf("%I64u %I64d\n",num,cnt);  
    }  
    return 0;  
}  

 其中，dfs即為深搜的一個函數。可經過預先計算得知深度不會超過16所以我們將前16個素數處理出來，已經足夠了。