首页 > 代码库 > hdu 2204 Eddy's爱好 容斥原理
hdu 2204 Eddy's爱好 容斥原理
题意:求出1-N里面能表示 成M^K的数有多少个。(N<=10^18)
1.如果i^B<=N(B>1),那么 (1~i)都能表示成M^K的形式。
2.如果i^4<=N,i^4可以由(i^2)^2来表示所以让指数为素数就能表示出所有了。
3。因为2^60>10^18, 所以只需要列出60以内的素数。
4.若果简单的按照以上对60以内的素数(17个)每次都pow(N,1.0/prime[i])(i<17);
这样就少考虑重复的情况,像4^3与8^2,指数都是素数他们都是2^6;
所以要利用容斥原理。
5,直接开方会有精度损失 加上eps = 1e-8就行了;
#include<cstdio> #include<cstring> #include<iostream> #include<cmath> using namespace std; #define ll __int64 const double eps = 1e-8; ll prim[18]={2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59}; ll n,ans; void dfs(ll index,ll len,ll s,ll num) { if(num==len) { ll temp=(pow(n*1.0,1.0/s)+eps)-1;//每次都会重复计算1^s,所以要减去,最后加上一个就行了 ans+=temp*(len&1?1:-1); return ; } if(index>=17) return ; if(s*prim[index]<=60) dfs(index+1,len,s*prim[index],num+1); dfs(index+1,len,s,num); } int main() { while(scanf("%I64d",&n)!=EOF) { ans=0; for(ll i=1;i<=3;i++) dfs(0,i,1,0); printf("%I64d\n",ans+1); } return 0; }
hdu 2204 Eddy's爱好 容斥原理
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。