传送门
题面：
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
1000000000000000000Sample Output
4
9
1001003332题目分析：
首先需要知道一个结论：在一个区间[1,n]中，能被开平方的数一共有 个。同理，在区间[1,n]中，能被开立方的数一共有
个.....更一般的，能够被开k次方的数一共会有
个数。
因为我们要求的是1到n间的可以构成M^K这种形式的数，我们上述的结论直接枚举每一个k进行求解。同时，我们可以发现，倘若k能够被质因数分解（k不是质数），则我们分解后的结果必定是两个质数的幂，而这两个质数的结果我们在之前必定也是统计过了的，因此对于k，我们只需要枚举质数即可。
观察数据范围可知，倘若底数为2，则要达到1e18，k最多达60即可，即我们只需要筛出[2,60]之间的质数即可。
然而这么做的话显然我们在某些情况下是计重了的，此时我们就需要用到万能的容斥原理啦。同时我们可以看出，因此我们最多只需要容斥三次即可。
ps：这个题在进行pow操作的时候，在将pow的double类型转化成longlong类型的时候，需要多加一个1e-8的常数，否则答案会出现一定偏差。
代码：
#include <bits/stdc++.h>
#define maxn 40
using namespace std;
typedef long long ll;
vector<ll>isprime;
const double eps=1e-8;
bool check(ll x){
for(ll i=2;i*i<=x;i++){
if(x%i==0) return 0;
}
return 1;
}
void init(){
isprime.push_back(2);
for(int i=3;i<70;i++){
if(check(i)) isprime.push_back(1ll*i);
}
}
int main()
{
init();
ll n;
while(cin>>n){
ll res=1;
int len=isprime.size();
for(int i=0;i<len;i++){
ll tmp=(ll)(pow(n,1.0/isprime[i])+eps);
if(tmp<2) break;
res+=tmp-1;
for(int j=i+1;j<len;j++){
tmp=(ll)(pow(n,1.0/(isprime[i]*isprime[j]))+eps);
if(tmp<2) break;
res-=tmp-1;
for(int k=j+1;k<len;k++){
tmp=(ll)(pow(n,1.0/(isprime[i]*isprime[j]*isprime[k]))+eps);
if(tmp<2) break;
res+=tmp-1;
}
}
}
cout<<res<<endl;
}
}