2013
12-21

# 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.

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.

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

2
1 3 1 5 1
1 11014 1 14409 9

Case 1: 9
Case 2: 736427

HintFor 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). 

/*

*/
#include<iostream>
#include<string.h>
#define size 100010
using namespace std;
struct Num
{
int count;
int prime[20];
}N[size];
__int64 elur[size];

void Elur()
{
elur[1]=1;
for(int i=0;i<size;i++) N[i].count=0;
for(int i=2;i<size;i++)
{
if(!elur[i])    //首先求素数
{
for(int j=i;j<size;j+=i)
{
if(!elur[j]) elur[j]=j;
elur[j]=elur[j]*(i-1)/i; //欧拉函数公式
N[j].prime[N[j].count]=i;
N[j].count++;
}
}
elur[i]+=elur[i-1];  //elur[i]表示前i个数的质因数的累加。
}
}

__int64 Inclusion_exclusion(int index , int b , int n)
{  //index表示此刻算到哪个质因数，b表示在1~b中计算被质因数整除的个数，指第二个区间的哪一个数。
__int64 r=0 , t;
for(int i=index;i<N[n].count;i++)  //x与y的最大公约数为k*p(p为质数)
{
t=b/N[n].prime[i];
r+=t-Inclusion_exclusion(i+1,t , n);  //因为防止有数被重复计算，所以根据容斥定理
}
return r;
}
int main()
{
int a , b, c, d , k;
int t ,tt=0;
Elur();
__int64 ans;
scanf("%d",&t);
while(t--)
{
scanf("%d%d%d%d%d",&a,&b,&c,&d,&k);
if(k==0)
{
printf("Case %d: 0\n",++tt);
continue;
}
if(b>d)
{
b^=d;
d^=b;
b^=d;
}
b=b/k;
d=d/k;
ans=elur[b];
for(int i=b+1;i<=d;i++)
{
ans+=b-Inclusion_exclusion(0,b,i);
}
printf("Case %d: %I64d\n",++tt,ans);
}
return 0;
}

1. 女人，如花。带着岁月的城市里一定有那么些人点缀着它的兴荣，因着善良因着美丽。祖国的大多数城市我都不知道，也是因为一个人认识一座城，便爱上了那座城市的美丽。

2. 给你一组数据吧：29 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 1000。此时的数据量还是很小的，耗时却不短。这种方法确实可以，当然或许还有其他的优化方案，但是优化只能针对某些数据，不太可能在所有情况下都能在可接受的时间内求解出答案。

3. bottes vernies blanches

I appreciate the efforts you men and women place in to share blogs on such sort of matters, it was certainly useful. Keep Posting!