HDU 3208 Integer’s Power

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 typedef long long LL;
 4 LL cnt[64];
 5 LL solve(LL x,int i = 0){
 6     if(x <= 3) return x;
 7     memset(cnt,0,sizeof cnt);
 8     for(i = 2; i < 3; ++i){
 9         unsigned long long tmp = pow((long double)x + 0.5,(long double)1.0/i);
10         //if(tmp <= 1) break;
11         cnt[i] = tmp - 1;
12     }
13     for(; i < 63; i++) {
14         unsigned long long d;
15         bool yc = false;
16         for(d = 2; !yc; d++) {
17             unsigned long long mi = 1;
18             for(int j = 0; !yc && j < i; j++) {
19                 mi *= d;
20                 if(mi > x) {
21                     yc = true;
22                 }
23             }
24             if(yc) break;
25         }
26         cnt[i] = d - 2;
27     }
28     cnt[1] = x;
29     for(int j = i-1; j > 0; --j){
30         for(int k = 1; k < j; ++k)
31             if(j%k == 0) cnt[k] -= cnt[j];
32     }
33     LL ret = cnt[1];
34     for(int j = 2; j < i; ++j)
35         ret += j*cnt[j];
36     return ret;
37 }
38 int main() {
39     LL a,b;
40     while(scanf("%I64d%I64d",&a,&b),a||b)
41         printf("%I64d\n",solve(b) - solve(a - 1));
42     return 0;
43 }