HDU - 1695 GCD （容斥原理+質因子分解）

Given 5 integers: a, b, c, d, k, you're to find x in a...b, y in c...d that GCD(x, y) = k. GCD(x, y) means the greatest common divisor of x and y. Since the number of choices may be very large, you're only required to output the total number of different number pairs. 

Please notice that, (x=5, y=7) and (x=7, y=5) are considered to be the same. 

Yoiu can assume that a = c = 1 in all test cases. 

Input

The input consists of several test cases. The first line of the input is the number of the cases. There are no more than 3,000 cases. 

Each case contains five integers: a, b, c, d, k, 0 < a <= b <= 100,000, 0 < c <= d <= 100,000, 0 <= k <= 100,000, as described above. 

Output

For each test case, print the number of choices. Use the format in the example. 

Sample Input

2
1 3 1 5 1
1 11014 1 14409 9      

Sample Output

Case 1: 9
Case 2: 736427
      

Hint

For the first sample input, all the 9 pairs of numbers are (1, 1), (1, 2), (1, 3), (1, 4), (1, 5), (2, 3), (2, 5), (3, 4), (3, 5).      

 解題思路：

求（1，b）區間和（1，d）區間裡面gcd(x, y) = k的數的對數（1<=x<=b , 1<= y <= d）。

先轉換成gcd(x/k,y/k)=1的對數，是以區間的範圍為(1,b/k)和(1,d/k)，這道題目還要求1-3 和 3-1 這種情況算成一種，是以隻需要限制x<y就可以了,

這裡使用了容斥定理：

容斥原理有好多寫法具體參考部落格：https://blog.csdn.net/qq_40707370/article/details/82428221

AC代碼：

#include<iostream>
#include<cstdio>
using namespace std;
typedef long long ll;
ll p[10],k;//數組p儲存質因子 long long型不同的質因子個數不超過10 
void getp(ll n)//分解質因子 
{
	k=0;
	for(int i=2;i*i<=n;i++)
	{
		if(n%i==0)
			p[k++]=i;
		while(n%i==0)
			n/=i;
	}
	if(n!=1)
	p[k++]=n;
}
ll nod(ll n)//容斥原理 
{
	ll i,j,top=0,que[1000],sum=0,t;
	que[top++]=-1;	
	for(i=0;i<k;i++)
	{
		t=top;
		for(j=0;j<t;j++)
			que[top++]=que[j]*p[i]*-1;
	}
	for(i=1;i<top;i++)
	{
		sum+=n/que[i]; 
	}
	return n-sum;//傳回區間（1，n）中與n是互質的個數 
}
int main()
{
	ll a,b,c,d,k,t,m,n;
	cin>>t;
	for(int i=1;i<=t;i++)
	{
		cin>>a>>b>>c>>d>>k;
		if(!k)
		{
			printf("Case %d: 0\n",i);
			continue;
		}
		b/=k;
		d/=k;
		if(b==0||d==0)//這一點剛開始沒考慮到，wa了，調試了好久好久才找到錯誤 
		{
			printf("Case %d: 0\n",i);
			continue;
		}
		if(b>d)
			swap(b,d);
			ll sum=d;//因為1與任何數互質，是以剛開始加d 
		for(int j=2;j<=b;j++)//在小區間（1，b)從2開始周遊，在區間（1，d)中找與之互質的數 
		{
			getp(j);
			sum=sum+nod(d)-nod(j-1); //減去node(j-1)是為了去重（1，2），（2，1）這種情況 
		}
		printf("Case %d: %lld\n",i,sum);
	}
	return 0;
}