题目描述：

解题思路：这题思路好想，n最多也就是20个不同的素数相乘，把所有可能的素数找到，然后枚举素数个数就行了。

n = p1^q1 + p2^q2 + p3 ^q3 + ... + pi ^qi;

约数个数也好找，有个约数个数定理：

 

对于一个大于1正整数n可以分解质因数：

则n的正约数的个数就是

。

其中a

₁、a

₂、a

₃…a

_k是p

₁、p

₂、p

_3，…p

_k的指数。

 

真正的难点在于剪枝：

从小到大dfs素数个数，后面的素数个数一定小于等于前面的素数个数。

这个很好想，既然能用大的素数，肯定也能用小的素数，所以如果大的素数个数比小的素数多，那就一定不是最优解。

比如n为10，可能会用到2 5 7这三个素数，如果用到了5，那肯定能用到2，而且2的个数一定>=5的个数。可能有人会问，那直接全用2不就行了，不一定，因为约数的个数f(n)并不恒大于a1*k2，看该题的样例就知道了。

注意：由上可知，搜索下一个素数个数时，前面的素数个数不可能为0（如果考虑为0会超时

 

附ac代码：

1 #include
       
         2 #include
        
          3 #include
         
           4 #include
          
            5 #include
           
             6 using namespace std; 7 typedef long long ll; 8 const int maxn = 111; 9 ll nu[maxn],prim[maxn];10 bool isprim[maxn];11 ll prime[30]={
     2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89};12 void euler() {13     memset(isprim, true, sizeof(isprim));14     isprim[1] = false;15     int len = 0;16     for(int i = 2; i <= 1000; ++i) {17         if(isprim[i]) prim[++len] = i;18         for(int j = 1; j <= len && i * prim[j] <= 100; ++j) {19             isprim[i * prim[j]] = false;20             if(i % prim[j] == 0) break;21         }22     }23 //    printf("%d",len);24 }25 ll n;26 ll maxx = 1e18, maxi = 0;27 void dfs(int now, ll anss, ll ansi, ll pre) {28 //    printf("%d %lld\n", now, anss);29      if(now == 20) return;30      if((ansi > maxi) || (ansi == maxi && maxx > anss)) {31          maxx = anss;32          maxi = ansi;33      }34      int i = 1;35      while(i <= pre) {36          37          if(anss > n / prim[now]) break;38         anss *=  prim[now];39          dfs(now + 1, anss, ansi * (i + 1), i);//因为ak-1>=ak，所以从前向后遍历素数，前面每个素数的个数都不会为0 40          i++;41      }42 }43      44 int main()45 {46     euler();47     ll sum = 1;48     int t;49     scanf("%d", &t);50     while(t--) {51         maxx = 1e18, maxi = 0;52         scanf("%lld", &n);53         dfs(1, 1, 1, 60);54         printf("%lld\n",maxi);55     }56     return 0;57 }