【HDU-2204- Eddy's爱好】 容斥原理

HDU-2204- Eddy’s爱好
题意就是给出一个数n，问1-n中有多少个数可以表示为m^k，m,k均为正整数且k>1
由于这里k是大于1的，所以我们想一下哪些k是可以被替代的，例如一个数如果可以被表示为$m^4$，那么他一定可以被表示为$(m^2)^2$,所以我们知道了只要枚举所有质数次幂的组合就可以了，同样当我们枚举2的整数次幂和3的整数次幂都会枚举到6，所以我们需要容斥一下，那么容斥的个数上界是多少呢，我们发现2*3*5*7=210>60,而2^60>1e18，所以容斥的个数上界是3，容斥枚举的质数上界为59。
容斥原理第一题代码

#include<stdio.h>
#include<iostream>
#include<algorithm>
using namespace std;
int prime[20]={
   2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59};
long long n,ans;
int i;//全局变量表示当前枚举的容斥是几个数的。
void dfs(int pos,int num,int p)
{if(p==0){long long tmp=pow(n,1.0/num);if(pow(tmp,(double)num)>n) tmp--;//注意精度tmp--;if(tmp>0){if(i&1) ans+=tmp;else ans-=tmp;}return ;}if(pos==17) return;if(num*prime[pos]<60) dfs(pos+1,num*prime[pos],p-1);dfs(pos+1,num,p);return ;
}
int main()
{while(scanf("%lld",&n)!=EOF){ans=0;for(i=1;i<=3;i++) dfs(0,1,i);printf("%lld\n",ans+1);}return 0;
}