GCD

题目连接：

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

T

a b c d k

Output

ans

Sample Input

1

1 3 1 5 1

Sample Output

9

Hint

题意

问你gcd(i,j)=k有多少对，其中b>=i>=a,d>=j>=c

其中a和c恒等于1

题解：

很显然，我们知道一个结论，gcd(i,j)=k,b>=i>=a,d>=j>=c这个恒等于

gcd(i,j)=1,b/k>=i>=1,d/k>=j>=1

然后怎么办呢？我们暴力枚举每一个1<=i<=b/k的数，看在1<=j<=d/k里面有多少个和他互质的就好了

这个我们可以用容斥来做。

代码

#include
    
     using namespace std;const int maxn = 2e5+5;vector
     
      pri[maxn];void pre(){    for(int i=2;i<100007;i++)    {        int now = i;        for(int j=2;j*j<=now;j++)        {            if(now%j==0)            {                pri[i].push_back(j);                while(now%j==0)                    now/=j;            }            if(now==1)break;        }        if(now>1)            pri[i].push_back(now);    }}int solve(int x,int tot){    int res = 0;    for(int i=1;i<(1<
      
       >j)&1)            {                num++;                tmp*=pri[x][j];            }        }        if(num%2==1)res+=tot/tmp;        else res-=tot/tmp;    }    return tot-res;}int main(){    pre();    int t;    scanf("%d",&t);    for(int cas=1;cas<=t;cas++)    {        int a,b,c,d,k;        scanf("%d%d%d%d%d",&a,&b,&c,&d,&k);        if(k==0)        {            printf("Case %d: 0\n",cas);            continue;        }        b/=k,d/=k;        if(b