HDU 2204 Eddy's爱好

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 typedef long long LL;
 4 const int maxn = 100;
 5 vector<int>g;
 6 const int p[] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67};
 7 void init(int r = 64) {
 8     g.clear();
 9     for(int i = 0; p[i] < r; ++i) {
10         for(int j = g.size()-1; j >= 0; --j)
11             if(abs(p[i]*g[j]) <= 63) g.push_back(-p[i]*g[j]);
12         g.push_back(p[i]);
13     }
14 }
15 int main() {
16     LL x;
17     init();
18     while(~scanf("%I64d",&x)) {
19         LL ret = 0;
20         for(int i = 0; i < g.size(); ++i) {
21             LL tmp = pow(x + .5,1.0/abs(g[i]));
22             if(g[i] < 0) ret -= tmp;
23             else ret += tmp;
24         }
25         printf("%I64d\n",ret - 1);
26     }
27     return 0;
28 }