最近看了很多容斥原理的题目,跟离散上学的不大一样了,有时候根本想不到,有些题目看了题解都不懂,凡是牵扯到位运算的我感觉都不简单。。。
题意:求x∈[1,b]和y∈[1,d]的区间内有多少组gcd(x,y)==k,其中(x,y)(y,x)算是一组
思路:先做一个小变换,b,d都除以k,问题变为求x∈[1,b/k]和y∈[1,d/k]的区间内有多少组gcd(x,y)==1
在此基础上,令b=b/k,d=d/k,假设b<>
对于[b+1,d]的部分,主要思想就是,首先把每个数据做因子分解,求出与其不互质的数据个数,b减去即可
这里就用到了容斥原理,Goal=可以被一个因子整除的个数-可以被两个因子整除的个数+可以被三个因子整除的个数(-1)^(n+1)(整除n个的个数)
假设x=6,因子为2,3,区间为[1,15],map[1|2]={2,4,6,8,10,12,14,}map[1|3]={3,6,9,12,15} map[2|2,3]={6,12}
Goal=7+5-2=10 所以与6互质的有5个
如果p(p!=1)是x的因子,那么在区间[1,d]中,有d/p个数与x不互质
假设x有num个因子,1除外,根据组合数学的公式C1+C2+……=2^num,枚举各类情况
2 1 3 1 5 1 1 11014 1 14409 9Sample Output
Case 1: 9 Case 2: 736427
#include#include #include #include #include using namespace std; #define ll long long #define MOD 1000000007 #define N 100010 int a,b,c,d,gg; int gcd(int a,int b) { if(b==0) return a; return gcd(b,a%b); } int lcm(int a, int b) { return a/gcd(a, b)*b; } int prime[N],vis[N]; int phi[N]; void init() { int i; for(i=2;i<=100000;i++) phi[i]=0; phi[1]=1; for(i=2;i<=100000;i++) if(!phi[i]) for(int j=i;j<=100000;j+=i) { if(!phi[j]) phi[j]=j; phi[j]=phi[j]/i*(i-1); } } int k; void Oula(int n) { k=0; for(int i=2;i 0; kk >>= 1, i++) { if (kk & 1) { ans = lcm(ans, p[i]); cnt++; } } if (!(cnt & 1)) ans = -ans; } int cal(int n) { num=0; for(int i=0;i >t; for(int cas=1;cas<=t;cas++) { ll ans=0; scanf("%d%d%d%d%d",&a,&b,&c,&d,&gg); cout<<"Case "<