GCD
Time Limit: 6000/3000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 3112 Accepted Submission(s): 1095
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
[cpp] view plaincopy
/*
題目大意：
給你a, b, c, d, k; 找出這樣的一隊 x, y， 使得 gcd(x , y) = k, 並且x ∈[1, b], y ∈ [1, d], 問有多少對符合要求的(x, y)。
------------------------------------------------------------------------------
思路: gcd(x, y) == k 說明x,y都能被k整除, 但是能被k整除的未必gcd=k , 必須還要滿足互質關系. 問題就轉化為了求1~a/k 和 1~b/k間互質對數的問題可以把a設置為小的那個數,
那麼以y>x來保持唯一性(題目要求, 比如[1,3] =[3,1] )
接下來份兩種情況:
1. y <= a , 那麼對數就是 1~a的歐拉函數的累計和(容易想到)
2. y >= a , 這個時候歐拉函數不能用了,怎麼做? 可以用容斥原理,把y與1~a互質對數問題轉換為y的質數因子在1~a范圍內能整除的個數(質數分解和容斥關系)，
*/
#include <iostream>
#include <stdio.h>
#include <memory.h>
#include<math.h>
#include <vector>
using namespace std;
const int N = 100005;
typedef long long LL;
#define maxn 100005
LL phi[N];
vector<LL> link[N];
int vis[1000000+5],c;
LL prime[79000];
void get_prime() //打印素數表模板
{
int i,j,n,m;
c=0;
n=1000000;
m=(int)sqrt(n+0.5);
memset(vis,0,sizeof(vis));
for(i=2;i<=m;i++)
if(!vis[i])
{
for(j=i*i;j<=n;j+=i)
vis[j]=1;
}
for(i=2;i<=n;i++) if(!vis[i])
prime[c++]=i;
}
void get_PHI() //模板 得到1->n之內 與n互質的數的個數 存入phi[n]
{
int i,j;
for (i = 1; i <= maxn; i++) phi[i] = i;
for (i = 2; i <= maxn; i += 2) phi[i] /= 2;
for (i = 3; i <= maxn; i += 2) if(phi[i] == i)
{
for (j = i; j <= maxn; j += i)
phi[j] = phi[j] / i * (i - 1);
}
}
void init() //求每一個數的質因數，vector儲存
{
LL i, j, k;
for(i = 1; i < N; i++)//求n的質因數 也是模板
{
k = i;
for(j = 0; prime[j]*prime[j] <= k; j++)
{
if(k%prime[j] == 0)
{
link[i].push_back(prime[j]);
while(k%prime[j] == 0)
k /= prime[j];
}
if(k == 1) break;
}
if(k > 1) link[i].push_back(k);
}
}
LL make_ans(LL num,LL n)//1到num中的所有數與n的m個質因子不互質的數的個數 注意是不互質哦 容斥原理
{
LL ans=0,tmp,i,j,flag;
for(i=1;i<(LL)(1<<link[n].size());i++)
{ //用二進制來1,0來表示第幾個素因子是否被用到,如m=3，三個因子是2,3,5，則i=3時二進制是011，表示第2、3個因子被用到
tmp=1,flag=0;
for(j=0;j<link[n].size();j++)
if(i&((LL)(1<<j)))//判斷第幾個因子目前被用到
flag++,tmp*=link[n][j];//第j個質因子link[n][j]
if(flag&1)//容斥原理，奇加偶減
ans+=num/tmp;
else
ans-=num/tmp;
}
return ans;
}
int main()
{
LL i, a, b, c, d, k, sum, t, zz = 1;//longlong型的數據 可以用%I64d 來輸入輸出
get_prime();
get_PHI();
init();
scanf("%I64d", &t);
while(t--)
{
scanf("%I64d %I64d %I64d %I64d %I64d", &a, &b, &c, &d, &k);
if(k == 0 || k > b || k > d)
{
printf("Case %I64d: 0\n", zz++);
continue;
}
if(b > d) swap(b, d);//保持d較大
b /= k;
d /= k;
sum = 0;
for(i = 1; i <= b; i++)
{
sum += phi[i];
}
for(i = b+1; i <= d; i++)
{
sum += b - make_ans(b, i);
}
printf("Case %I64d: %I64d\n", zz++, sum);
}
return 0;
}
