这个题真是太神奇了,搜索题。首先,打表肯定不行,这么大的数了。然后看了题解,用到了分解质因素的方法。我们可以举例来说明一下。比如12:

blob.png

从树根到叶子节点的乘积都是12的约数,所以12共有6个约数。

再者,任何一个数都可以分解成一个由质数相乘组成的数,如:

x = 2^x1*3^x2*5^x3......

由反质数的性质,有x1>x2>x3>....

搜索的意图就很明显了,从2的指数开始搜索。


题目地址:http://www.lydsy.com/JudgeOnline/problem.php?id=1053


代码:

Memory: 1288 KB
Time: 0 MS
Language: C++
Result: Accepted
#include<iostream>
using namespace std;
long long ans;
int n, now;
int prime[16] = {2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53};    //质数打表,代表树的深度
void dfs(int dep, long long tmp, int cnt){    //dep记录深度,tmp记录当前的积,cnt记录约数个数
    if(dep>=16)return;    //超出返回
    if(cnt>now){            //如果比当前数大,交换
        ans=tmp;
        now=cnt;
    }
    if(cnt==now && tmp<ans)ans=tmp;    //等于界限的情况
    for(int i=1;i<=63;i++){
        if(tmp*prime[dep]>n)break;    //剪枝
        dfs(dep+1, tmp*=prime[dep], cnt*(i+1));    //搜索下一层,传递当前的指数个数,(i+1)代表下一个约数加了进来
        }
}
int main()
{
    while(cin>>n){
        now=0;
        ans=2000000000;
        dfs(0, 1, 1);
        cout<<ans<<endl;
    }
    return 0;
}