HDU 3208 Integer’s Power

Integer’s Power

Time Limit: 1000ms

Memory Limit: 32768KB

This problem will be judged on HDU. Original ID: 3208
64-bit integer IO format: %I64d Java class name: Main

LMY and YY are number theory lovers. They like to find and solve some interesting number theory problems together. One day, they become interested in some special numbers, which can be expressed as powers of smaller numbers.

For example, 9=3^2, 64=2^6, 1000=10^3 …

For a given positive integer y, if we can find a largest integer k and a smallest positive integer x, such that x^k=y, then the power of y is regarded as k.
It is very easy to find the power of an integer. For example:

The power of 9 is 2.
The power of 64 is 6.
The power of 1000 is 3.
The power of 99 is 1.
The power of 1 does not exist.

But YY wants to calculate the sum of the power of the integers from a to b. It seems not easy. Can you help him?

Input

The input consists of multiple test cases.
For each test case, there is one line containing two integers a and b. (2<=a<=b<=10^18)

End of input is indicated by a line containing two zeros.

Output

For each test case, output the sum of the power of the integers from a to b.

Sample Input

2 10
248832 248832
0 0

Sample Output

13
5

Source

2009 Shanghai Invitation Contest Host by DHU

解题：容斥原理

表示$a^b$的数个数要减去$a^{ib},其中i>1的数个数，因为可以表示成a^{ib}也能表示a^b的形式，但是a^b不是最小表示$

 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
",solve(b) - solve(a - 1));
42     return 0;
43 }

View Code