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题解：很明显要用容斥去做，但1e18最多可以开64次方，64以内的素数有18个，但是2*3*5=30 所以容斥3层即可
1次方是不能算的 所以计算的时候都要减1 但是1可以写成1的任意次方 所以结果加1
#include<iostream> #include<cstdio> #include<algorithm> #include<cstring> #include<cmath> using namespace std; const int N=12; typedef long long ll; ll n,m,a[N]; int prime[70]; int ok[50],len; void init() { prime[1]=1; for(int i=2;i<=64;i++) { if(!prime[i]) { ok[len++]=i; for(int j=i+i;j<=64;j+=i) prime[j]=1; } } } int main() { init(); while(scanf("%lld",&n)!=EOF) { ll ans=0; for(int i=0;i<len;i++) { int tmp=pow(n,1.0/ok[i]); ans+=tmp-1; for(int j=i+1;j<len;j++) { tmp=pow(n,1.0/ok[i]/ok[j]); ans-=tmp-1; for(int k=j+1;k<len;k++) { tmp=pow(n,1.0/ok[i]/ok[j]/ok[k]); ans+=tmp-1; } } } cout<<ans+1<<endl; } return 0; }
