本文共 1045 字，大约阅读时间需要 3 分钟。

问题 C: Antiprime数

时间限制: 1 Sec  内存限制: 128 MB

题目描述

如果一个自然数n（n>=1），满足所有小于n的自然数（>=1）的约数个数都小于n的约数个数，则n是一个Antiprime数。譬如：1, 2, 4, 6, 12, 24。

任务：

编一个程序：

        读入自然数n。

2、 计算不大于n的最大Antiprime数。

输入

 读入一个整数，n（1 <= n <= 2 000 000 000）

输出

不大于n的最大Antiprime数。

样例输入

1000

样例输出

840

徐不可说：

1、由于n可以达到2*10^9，所以用枚举法会超出时间复杂度。

2、当n=2*10^9时，Antiprime数仅有1456个。所以可以把所有此类的数搜索并存储下来，同时记录下每个数的约数个数。把它们从小到大排序后，再逐一判断哪些是Antiprime数，取最大值即可。如n=15，则满足条件的数是1、2、4、6、和12，其约数个数分别是1、2、3、4、4和6，所以不大于15的Antiprime数有1、2、4、6、12，其中最大值是12。从小到大枚举每个质因数的使用个数（由数据范围限定最多枚举到23）

3、因为2^31接近2*10^9，所2的指数从31、30……往下搜。使用深度搜索。

  

#include
   
       using namespace std;long long n,maxx,num[12]={0,2,3,5,7,11,13,17,19,21,23},ans;  void findd(long long now,long long tot,long long u,long long v){       if(maxx
    
     now))       {           maxx=tot;         ans=now;       }       if(v>=11) return;       for(long long i=1;i<=u;i++)       {           now*=num[v];           if(now>n) return;           findd(now,tot*(1+i),i,v+1);       }   }    int main()   {        scanf("%I64d",&n);       findd(1,1,500,1);       cout<
    
   

转载地址：http://uotgn.baihongyu.com/