求1~n中与m互质的数的个数

发布时间:2017-3-28 4:23:59 编辑:www.fx114.net 分享查询网我要评论
本篇文章主要介绍了"求1~n中与m互质的数的个数",主要涉及到求1~n中与m互质的数的个数方面的内容,对于求1~n中与m互质的数的个数感兴趣的同学可以参考一下。

dfs版: LL fac[80],num; void Divide(LL m) { num=0; if(!vis[m]) { fac[num++]=m; return; } for(int i=0;i<k&&m>1;i++) { if(m%prime[i]==0) { fac[num++]=prime[i]; while(m%prime[i]==0) m/=prime[i]; if(m>1&&!vis[m]) { fac[num++]=m; return; } } } } LL anss; void dfs(int k,int l,int s,int a) { if(k==num){ if(l&1) anss-=a/s; else anss+=a/s; return ; } dfs(k+1,l,s,a); dfs(k+1,l+1,s*fac[k],a); return ; } void work(int n,int m) { anss=0; Divide(m); dfs(0,0,1,n); } 非dfs版: LL fac[80],num; void Divide(LL m) { num=0; for(int i=0;prime[i]*prime[i]<=m;i++) if(m%prime[i]==0) { fac[num++]=prime[i]; while(m%prime[i]==0) m/=prime[i]; } if(m>1) fac[num++]=m; } LL work(LL n,LL m) { LL sum=0; Divide(m); for(int i=1;i<(1<<num);i++) { LL tmp=1,t=0; for(int j=0;j<num;j++) if((1<<j)&i) t++,tmp*=fac[j]; if(t&1) sum+=n/tmp; else sum-=n/tmp; } return n-sum; }

上一篇:hdu3518(后缀数组)
下一篇:DXUT11框架浅析(5)--基础函数

相关文章

相关评论

本站评论功能暂时取消,后续此功能例行通知。

一、不得利用本站危害国家安全、泄露国家秘密,不得侵犯国家社会集体的和公民的合法权益,不得利用本站制作、复制和传播不法有害信息!

二、互相尊重,对自己的言论和行为负责。

好贷网好贷款