HDOJ 题目1695 GCD（欧拉函数，容斥原理）

GCD

Time Limit: 6000/3000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)

Total Submission(s): 6219    Accepted Submission(s): 2279

Problem Description 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).
   
    
        

Source 2008 “Sunline Cup” National Invitational Contest  

Recommend wangye   |   We have carefully selected several similar problems for you:   1689  1693  1691  1698  1692   思路：

转载请注明出处，谢谢 http://blog.csdn.net/ACM_cxlove?viewmode=contents           by---cxlove

很NB的数论题啊。

求1~a中的任意x,和1~b中任意y能组成gcd(x,y)=k的对数，二元组是无序的。

首先想到暴力，1-a中k的倍数的数与1-b中k的倍数的数，如果gcd(x,y)=k,则计数，显然肯定行不通。

x与y只有公因子k,则说明gcd（x/k,y/k）=1，貌似有点进展，求1~a/k,和1~b/k中的互质的对数。

枚举1~a/k中的任意一个数i,求1~b/k中与其互质的个数然后叠加？想法是对的，由于题目要求不重复的，即要避免(x,y)(y,x)这样的情况

回到问题求[1,a/k],[1,b/k]中的互质对数，我们令a/k>=b/k  ,对于[1,a/k]中的i,如果i<=b/k,便 是求1~i-1中与i互质的个数，即求i的欧拉函数值。

对于i>a/k的情况，只有将i质因子分解，然后容斥原理了，参考了别人的写法，发现以前写的容斥弱爆了，不过发现以前自己写的好理解。

欧拉函数和，即法雷级数?会溢出，小心 WA

ac代码

#include<stdio.h>
#include<string.h>
__int64 e[100005];
__int64 pri[100005][10],num[100005];
void fun()
{
	int i,j,k;
	memset(pri,0,sizeof(pri));
	memset(num,0,sizeof(num));
	for(i=1;i<100005;i++)
		e[i]=i;
	for(i=2;i<100005;i++)
	{
		if(e[i]==i)
		{
			e[i]=i-1;
			for(j=2;j*i<100005;j++)
			{
				e[i*j]=e[i*j]*(i-1)/i;
				pri[i*j][num[i*j]++]=i;
			}
		}
		e[i]+=e[i-1];
	}
}
__int64 dfs(int ii,int b,int now)
{
	__int64 ans=0;
	int i;
	for(i=ii;i<num[now];i++)
	{
		ans+=b/pri[now][i]-dfs(i+1,b/pri[now][i],now);
	}
	return ans;
}
int main()
{
	int a,b,c,d,k,t,cot=0;
	fun();
	scanf("%d",&t);
	while(t--)
	{
		int temp,i;
		__int64 ans;
		scanf("%d%d%d%d%d",&a,&b,&c,&d,&k);
		printf("Case %d: ",++cot);
		if(k==0)
		{
			printf("0\n");
			continue;
		}
		a=b/k;b=d/k;
		if(a<b)
		{
			temp=a;
			a=b;
			b=temp;
		}
		ans=e[b];
		for(i=b+1;i<=a;i++)
		{
			ans+=b-dfs(0,b,i);
		}
		printf("%I64d\n",ans);
	}
}