hdu 1695 GCD (欧拉函数+容斥原理)

GCD

Time Limit: 6000/3000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 5064 Accepted Submission(s): 1818

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

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 1691 1692 1697 1696

参考： http://blog.csdn.net/xiaotaoqibao/article/details/5772486

思路：

题目意思不难已知给定k,x,y求 1<=a<=x 1<=b<=y 中满足 gcd(a,b)=k 的(a,b)对数。（注意数对是无序的）。 1<=x,y<=10w, 0<=k<=10w

题目有比较恶心的一点，数据有k==0的，这时显然答案是0，没有2个数的gcd为0。

首先，gcd是没啥用的。因为约掉gcd后两个数互质。于是我们可以让x/=k y/=k并且假设 x<=y

然后题目变成了 2个数分别在区间[1..x]和[1..y]中的互质数有多少对。

大体思路：

枚举[1..y]中每个数i 判断[1..min(x,i)]中有多少数与i互质，统计个数。（注意，枚举的是比较大的区间[1..y]）。

显然如果i是质数，则[1..min(x,i)]中与i互质的个数是全体的个数或者i-1个。（取决于x和i的大小）。

当i不是质数时，i分解质因数后，质因数的次数不影响结果。我们看另外那个区间有多少个和i不互质（减一下就好了），于是我们只要看另外那个区间中有多少个数是i质因数的倍数就好了。

区间[1..w]中 p的倍数显然有 w/p个。

我们枚举i的质因数利用容斥原理：

看另外那个区间有多少个数与i不互质。

容斥原理的具体如下：

区间中与i不互质的个数 = （区间中i的每个质因数的倍数个数）-（区间中i的每两个质因数乘积的倍数）+（区间中i的每3个质因数的成绩的倍数个数）-（区间中i的每4个质因数的乘积）+...

于是问题变成了统计每个数的不同质因数的个数而忽略次数。这个可以用筛法。具体做法如下：

对每个数保存一个真质因数的列表。初始每个列表的长度为0。然后从2开始，分别检查每个数的列表长度，如果列表长度不为0，则这个数是合数，跳过；如果这个长度为0，则我们找到了一个质数，同时再把这个数的倍数（不包含本身）的列表里加入这个数。

这样筛一次下来，我们保存了每个数的真质因数列表，问题得到解决，还要注意结果用要用__int64。

 1 ///218MS    7256K    1385 B    G++    
 2 //容斥原理+欧拉函数 
 3 #include<stdio.h>
 4 #include<string.h>
 5 #include<string.h>
 6 #define N 100005
 7 int ss[N][15]; //质因数 
 8 int num[N]; //不同质因数个数 
 9 __int64 euler[N]; //euler[i]:[1,i]的欧拉数和 
10 void init()
11 {
12     memset(ss,0,sizeof(ss));
13     memset(euler,0,sizeof(euler));
14     euler[1]=1;
15     for(int i=2;i<N;i++){
16         if(!euler[i]){ //质数 
17             for(int j=i;j<N;j+=i){
18                 if(!euler[j]) euler[j]=j;            
19                 euler[j]=euler[j]*(i-1)/i;
20                 ss[j][num[j]++]=i; //记录质因数 
21             }
22         }
23         euler[i]+=euler[i-1];
24         //printf("*%d %d
",i,euler[i]);
25     }  
26 } 
27 __int64 dfs(int a,int b,int q) //容斥原理 
28 {
29     __int64 res=0;
30     for(int i=a;i<num[q];i++){
31         res+=b/ss[q][i]-dfs(i+1,b/ss[q][i],q);
32     }
33     return res;
34 }
35 int main(void)
36 {
37     int t,cas=1;
38     int a,b,c,d,k;
39     init();
40     scanf("%d",&t);
41     while(t--)
42     {
43         scanf("%d%d%d%d%d",&a,&b,&c,&d,&k);
44         if(k==0){
45             printf("Case %d: 0
",cas++);continue;
46         }
47         b/=k;
48         d/=k; //题目变成[1,b]与[1,d]间的互质的数有多少对  
49         if(b>d){
50             int temp=b;b=d;d=temp;
51         }
52         __int64 res=euler[b];
53         for(int i=b+1;i<=d;i++){
54             res+=b-dfs(0,b,i);
55         }
56         printf("Case %d: %I64d
",cas++,res);
57     }
58     return 0;
59 }