【HDU】1695 - GCD（欧拉函数 & 容斥原理）
【HDU】1695 - GCD（欧拉函数 & 容斥原理）
点击打开题目
GCD
Time Limit: 6000/3000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 9524 Accepted Submission(s): 3544
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 9Sample 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
这是道很好的题，首先要想到把问题化简，b和d同时除以k，然后在 [ 1 , b ] [ 1 , d ] 两个区间找互质数对。（如果x，y互质，同时乘 k 就是集合中对应的数，但是这样想问题就简化很多）
然后解这个又是个问题，我们假设 b <= d ，然后在 [ 1 , b ] 中求一个欧拉函数的和，再在 [ b + 1 , d ] 中用容斥原理求 [ 1 , b ] 中与其互质的数的个数之和。
最后的总和就是结果，这里要注意，欧拉函数的求法要打表，要不会超时。代码如下：
#include <cstdio>
#include <algorithm>
using namespace std;
int p[1000000];
__int64 eu[100005];
int ant;
void pr(int x)
{
ant = 0;
for (int i = 2 ; i * i <= x ; i++)
{
if (x % i == 0)
{
p[ant++] = i;
while (x % i == 0)
x /= i;
}
}
if (x > 1)
p[ant++] = x;
}
void Eular() //求n的欧拉函数
{
eu[1] = 1;
for (int i = 2 ; i <= 100000 ; i++)
{
if (!eu[i]) //之前没有求过
{
for (int j = i ; j <= 100000 ; j += i) //i的倍数的欧拉函数
{
if (!eu[j])
eu[j] = j;
eu[j] -= eu[j] / i;
}
}
eu[i] += eu[i-1];
}
}
__int64 solve(int n) //小于等于n且是k的倍数的数
{
__int64 sum = 0;
for (__int64 i = 1 ; i < (__int64)1 << ant ; i++)
{
int v = 1;
int m = 0;
for (int j = 0 ; j < ant ; j++)
{
if (((__int64)1 << j) & i)
{
v *= p[j];
m++;
}
}
if (m & 1)
sum += n / v;
else
sum -= n / v;
}
return sum;
}
int main()
{
int a,b,c,d,k;
int u;
int num = 1;
__int64 ans;
Eular();
scanf ("%d",&u);
while (u--)
{
scanf ("%d %d %d %d %d",&a,&b,&c,&d,&k);
printf ("Case %d: ",num++);
if (k == 0)
{
printf ("0\n");
continue;
}
pr(k);
b /= k;
d /= k;
if (b > d)
swap(b,d);
ans = eu[b];
for (int i = b + 1 ; i <= d ; i++)
{
pr(i);
ans += b - solve(b);
}
printf ("%I64d\n",ans);
}
return 0;
}腾讯云开发者
