题目大意：找出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个素数处理出来，已经足够了。

参考文献：

http://baike.baidu.com/view/1780622.htm

by:Jsun_moon http://blog.csdn.net/Jsun_moon