Eddy's爱好 HDU - 2204

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

题意：给你一个正整数n，求出1到N之间有多少数能狗表示成M^K的形式；

题目分析：

任何一个数都能分解成素数相乘的形式，所以指数K分解成素因子相乘的形式

M^k可以分解成 (M^(k*p)) p是素数

这么我们只要枚举素因子就好了

由于数据 所以只要枚举60以内的素数就够了

然后因为2*3*5*7就超过60了 做容斥原理就最多就只有三次

#include<cstdio> #include<iostream> #include<cmath> using namespace std; int p[]={2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59}; long long ans,n; void dfs(int cur,int s,int cnt) { long long t=(long long)pow(n,1.0/s); if(t>1) { if(cnt&1) ans+=t-1; else ans-=t-1; } if(cnt>2) return ; for(int i=cur+1;i<17;i++) dfs(i,s*p[i],cnt+1); } int main() { while(scanf("%lld",&n)!=EOF) { ans=1;///1不满足容斥原理，但满足题目中的条件 for(int i=0;i<17;i++) dfs(i,p[i],1); cout<<ans<<endl; } return 0; }