zoj2562 反素数

这题1 <= n <= 10¹⁶，暴力肯定是TLM，所以看了大牛求解小于N的反素数的算法，思路大致是这样的：

性质1：一个反素数的质因子一定是从2开始的若干个连续质数.

因此可以枚举素因子，2,3,5,7,11,13,17,19,23,29,31,37,41,43,47。。最多也就这么几个。

性质2：若有p=2^a1*3^a2*5^a3*......，则必有a1>=a2>=a3>=............an.

另外，如何求p的正约数个数呢，答案就是(a1+1)*(a2+1)*(a3+1)*..........(an=1)

如：p=6=2^1*3^1,故6的约束个数为（1+1）*(1+1)=4 ......等等

然后就是按照素因子递增的顺序逐个搜索，然后枚举每个质因子的个数

 1 #include<stdio.h>
 2 typedef long long LL;
 3 LL N;
 4 LL BestSum;
 5 LL BestRes;
 6 LL prime[16]={2,3,5,7,11,13,17,19,23,29,31,37,41,43,47};
 7 
 8 void work(LL res,LL sum,LL k,LL limit)
 9 {
10  if(res>N)
11   return;
12  if(BestSum<sum)
13  {
14   BestSum=sum;BestRes=res;
15  }
16  else if(BestSum==sum&&BestRes>res)
17   BestRes=res;
18  if(k>=16)
19   return;
20  LL p=prime[k];
21  int i;
22  for(i=1;i<limit;i++,p*=prime[k])
23  {
24   if(res*p>N)
25    break;
26   work(res*p,sum*(i+1),k+1,i+1);
27  }
28 }
29 
30 int main()
31 {
32  while(~scanf("%lld",&N))
33  {
34   BestSum=1;
35   BestRes=1;
36   work(1,1,0,50);
37   printf("%lld
",BestRes);
38  }
39 }
40 
41