HDU 2204 Eddy's爱好

Eddy's爱好

Time Limit: 1000ms

Memory Limit: 32768KB

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

 

Ignatius 喜欢收集蝴蝶标本和邮票，但是Eddy的爱好很特别，他对数字比较感兴趣，他曾经一度沉迷于素数，而现在他对于一些新的特殊数比较有兴趣。
这些特殊数是这样的：这些数都能表示成M^K，M和K是正整数且K>1。
正当他再度沉迷的时候，他发现不知道什么时候才能知道这样的数字的数量，因此他又求助于你这位聪明的程序员，请你帮他用程序解决这个问题。
为了简化，问题是这样的：给你一个正整数N，确定在1到N之间有多少个可以表示成M^K（K>1)的数。

 

Input

本题有多组测试数据，每组包含一个整数N，1<=N<=1000000000000000000(10^18).

 

Output

对于每组输入，请输出在在1到N之间形式如M^K的数的总数。
每组输出占一行。

 

Sample Input

10
36
1000000000000000000

Sample Output

4
9
1001003332

解题：容斥原理来一发

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