1053: [HAOI2007]反素数ant

思路

　　首先一个结论，对于一个数$n = p_1^{a_1}p_2^{a_2}...p_k^{a_k}$，它的因数的个数是$(a_1+1)(a_2+1)...(a_k+1)$，而且对于2,000,000,000，只要将素数2*3*5*...*31就比它大了，所以，可以搜索2,3,5...31这些素数的幂，然后取出最优解。

　　参考黄学长的博客。

代码

 1 #include<cstdio>
 2 #include<algorithm>
 3 #include<cstring>
 4 #include<iostream>
 5 
 6 using namespace std;
 7 typedef long long LL;
 8 
 9 int pri[20] = {0,2,3,5,7,11,13,17,19,23,29,31};
10 int Ans = 0,n;int Cnt = 0;
11 
12 void dfs(LL now,int p,int cnt,int last) { 
13     if (p == 12) {
14         if (now > Ans && cnt > Cnt) {Ans = now;Cnt = cnt;}
15         if (now <= Ans && cnt >= Cnt) {Ans = now;Cnt = cnt;}
16         return ;
17     }
18     int t = 1;
19     for (int i=0; i<=last; ++i) { // 枚举当前这个素数的幂
20         dfs(now*t,p+1,cnt*(i+1),i); // 当前素数的幂为i    
21         t *= pri[p];
22         if (now * t > n) break;
23     }
24 }
25 int main() {
26     cin >> n;
27     dfs(1LL,1,1,30);
28     cout << Ans;
29     return 0;
30 }