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

发布时间:2016-12-9 2:17:31 编辑: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)--基础函数

相关文章

相关评论