HDU 1695 GCD （容斥原理）

HDU 1695

题意：求有多少对(x,y), (1<=x<=b,1<=y<=d), 满足gcd(x,y)=k。

题解：注意到gcd(x,y)=k,说明x,y都能被k整除，那么gcd(x/k,y/k)=1,于是本题就可以转化为求在两个区间内寻找有多少对数互质。假设b<=d,我们可以在中枚举数i，对于每一个i，我们只需找到在[1,min( i-1,b/k ) ]中与i互质的个数，最后依次相加就可得到结果。当i<=b/k时可以用欧拉函数phi( )求与i互质的个数。

当b/k < i <= d/k时，区间中与i互质的个数 = b/k - （区间中与i不互质的个数）。

区间中与i不互质的数则就是i中素因子的倍数，将它们相加则就是答案，但是由于会有重叠部分，比如6既是2的倍数又是3的倍数，此时就可以用容斥原理来求解。

AC代码：

#include<bits/stdc++.h>using namespace std;typedef long long ll;const int N=100010;ll euler[N];int num[N];int p[N][20];void init()//欧拉函数phi() {	euler[1]=1;	for(int i=2;i<N;i++){		if(!euler[i]){			for(int j=i;j<N;j+=i){ //注意是 j+=i 				if(!euler[j])euler[j]=j;				euler[j] = euler[j]*(i-1)/i;				p[j][num[j]++] = i;				//cout<<"i="<<i<<endl;			}		}		euler[i] += euler[i-1];	}	//for(int i=1;i<=10;i++)cout<<euler[i]<<endl;}int solve(int b,int n)//区间中与 b 不互质的个数{	int ans=0;	for(int i = 1; i < (1<<num[b]); i++){		int cnt = 0;		int m = 1;		for(int j = 0; j< num[b];j++){			if((1<<j) & i){				cnt++;				m *= p[b][j]; //p[b][j]是质因数 			}		}		//奇加偶减 		if(cnt & 1) ans += n/m;		else ans -= n/m;	}	return ans;}int main(){	int t,a,b,c,d;	int k;	init();	//cout<<"finish"<<endl; 	scanf("%d",&t);	int cas=1;	while(t--)	{		scanf("%d%d%d%d%d",&a,&b,&c,&d,&k);		PRintf("Case %d: ",cas++);		if(k==0){			cout<<"0"<<endl;			continue;		}		if(b>d)swap(b,d);		b /= k;		d /= k;		ll ans=euler[b];		for(int i = b + 1; i <= d;i++){			ans += b-solve(i,b);		}		cout<<ans<<endl;	}	return 0;}/*21 3 1 5 11 11014 1 14409 9*/