题解：
其实就是求1-n之中拥有最多约数的数
一个数x的质因数分解为p1^e1*p2^e2*...*pn^en,则正因数的个数为(e1+1)(e2+1)...(en+1)
那么发现，正因数的个数和p没有关系
那么p越小越好
于是，若x是最好的,且x=p1^e1*p2^e2*...*pn^en，则e1<e2<e3<..en，且p1=2,p2=3....
那么这个p就不会很大，所以枚举的范围就大大缩小了
代码：
#include<bits/stdc++.h> using namespace std; typedef long long LL; typedef pair<int,int> PII; const int MX=1e2+5; const int INF=0x3f3f3f3f; int ans; LL id,n,prime[MX],psz,vis[MX]; void prime_init() { vis[1]=1; for(int i=2;i<MX;i++) { if(vis[i])continue; prime[++psz]=i; for(int j=2*i;j<MX;j+=i)vis[j]=1; } psz=17; } void DFS(LL s,int cnt,int p,int bo) { if(cnt>ans||(cnt==ans&&s<id)) { ans=cnt; id=s; } for(int i=1;i<=bo&&(double)s*prime[p]<=n;i++) { s*=prime[p]; DFS(s,cnt*(i+1),p+1,i); } } int main() { prime_init(); scanf("%I64d",&n); ans=id=1; DFS(1,1,1,100); printf("%d\n",id); }
原文：http://www.cnblogs.com/xuanyiming/p/7627046.html