UVa 11752 (素数筛选 快速幂) The Super Powers

 1 #include <cstdio>
 2 #include <cmath>
 3 #include <set>
 4 #include <cassert>
 5 using namespace std;
 6 
 7 typedef unsigned long long ULL;
 8 typedef set<ULL>::iterator It;
 9 bool vis[70];
10 
11 ULL POW(int a, int p)
12 {
13     ULL ans = 1, base = a;
14     while(p)
15     {
16         if(p & 1ULL) ans *= base;
17         base *= base;
18         p >>= 1;
19     }
20     return ans;
21 }
22 
23 int main()
24 {
25     for(int i = 2; i <= 64; i++) if(!vis[i])
26         for(int j = i * i; j <= 64; j += i) vis[j] = true;
27 
28     set<ULL> ans;
29     ans.insert(1);
30     for(int base = 2; base < 65536; base++)
31         for(int p = 4; p < (int)ceil(64.0 * log(2.0) / log(base)); p++) if(vis[p])
32         {
33             ULL v = POW(base, p);
34             assert(v != 1ULL); assert(v != 0);
35             if(!ans.count(v)) ans.insert(v);
36         }
37 
38     for(It i = ans.begin(); i != ans.end(); i++)
39         printf("%llu\n", *i);
40 
41 
42     return 0;
43 }