hdu 4135 Co-prime(容斥原理)

hdu 4135 Co-prime(容斥原理)

题目：​​b]内与n互质的数的个数。

分析：单纯来逐个判断互质统计结果肯定会超时，那么可以对n素因子分解，以素因子的个数作为循环的上界（第二层循环），第一层是枚举素因子，运用容斥原理来统计不互质的个数，最后再用总数减去不互质的个数就是互质的个数。【容斥原理也就是提供了这样间接求解的思想：先不考虑重叠的情况，把包含于某内容中的所有对象的数目先计算出来，然后再把计数时重复计算的数目排斥出去。容斥原理是用来求多个集合的并集的一种方法: |S |= |奇数个集合的并集| - |偶数个集合的并集| （奇加偶减）这样 避开了用值很大的数字b作为循环上界，最后直接用b-a+1减去互质个数即可。二进制枚举，枚举的对象在第二层】

#include #includeusing namespace std;const int maxn=1e7+10;typedef long long LL;LL sta[maxn],top=0;void fenjie(LL m){ top=0; for(int i=2;i*i<=m;i++){ if(m%i==0){ sta[top++]=i; while(m%i==0) m/=i; } } if(m>1)sta[top++]=m;}int main(){ //freopen("cin.txt","r",stdin); LL t,ca=0; LL A,B,N; cin>>t; while(t--){ scanf("%lld%lld%lld",&A,&B,&N); fenjie(N); LL ans=0; for(int i=1;i<(1<B)break; } if(sum&1)ans+=(B/temp-(A-1)/temp); else ans-=(B/temp-(A-1)/temp); } printf("Case #%lld: %lld\n",++ca,B-A+1-ans); } return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。