HDU 1695

題意：求有多少對(duì)(x,y), (1<=x<=b,1<=y<=d), 滿足gcd(x,y)=k。

題解：注意到gcd(x,y)=k,說(shuō)明x,y都能被k整除，那么gcd(x/k,y/k)=1,于是本題就可以轉(zhuǎn)化為求在兩個(gè)區(qū)間內(nèi)尋找有多少對(duì)數(shù)互質(zhì)。假設(shè)b<=d,我們可以在中枚舉數(shù)i，對(duì)于每一個(gè)i，我們只需找到在[1,min( i-1,b/k ) ]中與i互質(zhì)的個(gè)數(shù)，最后依次相加就可得到結(jié)果。當(dāng)i<=b/k時(shí)可以用歐拉函數(shù)phi( )求與i互質(zhì)的個(gè)數(shù)。

當(dāng)b/k < i <= d/k時(shí)，區(qū)間中與i互質(zhì)的個(gè)數(shù) = b/k - （區(qū)間中與i不互質(zhì)的個(gè)數(shù)）。

區(qū)間中與i不互質(zhì)的數(shù)則就是i中素因子的倍數(shù)，將它們相加則就是答案，但是由于會(huì)有重疊部分，比如6既是2的倍數(shù)又是3的倍數(shù)，此時(shí)就可以用容斥原理來(lái)求解。

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()//歐拉函數(shù)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)//區(qū)間中與 b 不互質(zhì)的個(gè)數(shù){	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]是質(zhì)因數(shù) 			}		}		//奇加偶減 		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*/