超级幂分析

题意:如果一个数至少是两个不同的正整数的幂,那么它被称为超级幂,按升序输出1至2^64-1之间的所有超级幂。

 

2.解题思路:本题要求找出1~2^64-1之间所有的超级幂。根据题意,不难知道这样的数的幂次一定是一个合数。而最大的幂次肯定不超过64,因此只需要去除4~64之间所有的素数即可,而这些素数可以事先打表。接下来开始枚举底数和幂次。由于幂次最多只有不超过60个,每个幂次对应的底数不超过10^5个,因此时间复杂度可以承受。

但这里还有一个问题:如何知道枚举到哪个幂次就停止枚举呢?很简单,只需要实现从2^64-1开始,计算出以i为底数的最大幂次的边界cnt即可。当cnt<4时即可中断枚举底数。注意:本题应该使用ull类型,同时为了防止重复,把结果存入set中。


[cpp]  view plain  copy
  1. #include <iostream>  
  2. #include <string.h>  
  3. #include <stdio.h>  
  4. #include <math.h>  
  5. #include <set>  
  6.   
  7. using namespace std;  
  8. typedef unsigned long long LL;  
  9.   
  10. bool prime[70];  
  11.   
  12. set<LL> s;  
  13. set<LL>::iterator it;  
  14.   
  15. int top(int a)  
  16. {  
  17.     return ceil(64/(log(a)/log(2.0))) - 1;  
  18. }  
  19.   
  20. void isprime()  
  21. {  
  22.     int i,j;  
  23.     memset(prime,true,sizeof(prime));  
  24.     for(i=2;i<70;i++)  
  25.     {  
  26.         if(prime[i])  
  27.         {  
  28.             for(j=i+i;j<70;j+=i)  
  29.                 prime[j] = false;  
  30.         }  
  31.     }  
  32. }  
  33.   
  34. int main()  
  35. {  
  36.     isprime();  
  37.     s.clear();  
  38.     cout<<"1"<<endl;  
  39.     for(LL i = 2;i<(1<<16);i++)  
  40.     {  
  41.         int tp = top(i);  
  42.         LL num = i;  
  43.         for(int j=2;j<=tp;j++)  
  44.         {  
  45.             num *= i;  
  46.             if(prime[j]) continue;  
  47.             if(s.count(num) == 0) s.insert(num);  
  48.         }  
  49.     }  
  50.     for(it = s.begin();it != s.end();it++)  
  51.         cout<<*it<<endl;  
  52.     return 0;  
  53. }  

上文来自:http://blog.csdn.net/acdreamers/article/details/12620809
http://www.07net01.com/2015/05/850401.html
相关文章
相关标签/搜索