首页 > 代码库 > HDU4135Co-prime（容斥原理）
HDU4135Co-prime（容斥原理）
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=4135
题目解析：
给你一个闭区间[A,B](1 <= A <= B <= 1015),以及一个正整数N，求[A,B]中与N互质的个数，可以先求[1,B]中与N互质的个数，在求[1,A-1]中与N互质的个数。之后两结果相减便得到答案。另外这题只要知道质因数的性质就很容易做了。任意一个正整数（除了1）都可以分解成有限个质数因子的乘积。那么假如两个数互质，那么这两个数没有相同质因子。所以若一个数跟n不互质，那么这个的数的质因子肯定也有属于n的质因子，那么就用容斥原理求出所有跟n不互质的所有数的个数。然后再用总的减去即可。
#include <iostream>#include <stdio.h>#include <string.h>#include <algorithm>#include <queue>using namespace std;typedef __int64 ll;ll x,b,n,sum,sum2,top,a[10001];ll gcd(ll A,ll B){ return B==0?A:gcd(B,A%B);}void dfs(ll now,ll num,ll lcm,ll &sum){ lcm=a[now]/gcd(a[now],lcm)*lcm; if(num&1) { sum+=b/lcm; } else { sum-=b/lcm; } for(int i=now+1; i<top; i++) dfs(i,num+1,lcm,sum);}void dfs2(ll now,ll num,ll lcm,ll &sum2){ lcm=a[now]/gcd(a[now],lcm)*lcm; if(num&1) { sum2+=(x-1)/lcm; } else { sum2-=(x-1)/lcm; } for(int i=now+1; i<top; i++) dfs2(i,num+1,lcm,sum2);}int main(){ int T; ll temp; scanf("%d",&T); for(int K=1; K<=T; K++) { scanf("%I64d%I64d%I64d",&x,&b,&n); sum=0; sum2=0; top=0; temp=n; for(int i=2; i*i<=temp; i++) { if(temp%i==0) { temp/=i; a[top++]=i; while(temp%i==0) { temp/=i; } } } if(temp!=1) a[top++]=temp; for(int i=0; i<top; i++) { dfs(i,1,a[i],sum); } for(int i=0; i<top; i++) { dfs2(i,1,a[i],sum2); } sum=(b-x+1)-(sum-sum2); printf("Case #%d: %I64d\n",K,sum); } return 0;}
HDU4135Co-prime（容斥原理）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。