HYSBZ 2301

 1 /***
 2 对于给出的n个询问，每次求有多少个数对(x,y)，满足a≤x≤b，c≤y≤d，且gcd(x,y) = k，gcd(x,y)函数为x和y的最大公约数
 3 **/
 4 #include <iostream>
 5 #include <cstdio>
 6 #include <algorithm>
 7 
 8 using namespace std;
 9 const int maxn = 50010;
10 int isprime[maxn],prime[maxn],mu[maxn],sum[maxn];
11 
12 int t,a,b,c,d,k;
13 int cnt;
14 void mobius(int n){
15     int i,j;
16     cnt =0;
17     mu[1] =1;
18     for(i=2;i<=n;i++){
19         if(!isprime[i]){
20             prime[cnt++] = i;
21             mu[i] = -1;
22         }
23         for(j=0;j<cnt&&i*prime[j]<=n;j++){
24             isprime[i*prime[j]] = 1;
25             if(i%prime[j])
26                 mu[i*prime[j] ] = -mu[i];
27             else{
28                 mu[i*prime[j]] = 0;
29                 break;
30             }
31         }
32     }
33 }
34 
35 long long solve(int n,int m){
36     int i,la;
37     long long ret =0;
38     if(n>m)
39         swap(n,m);
40     for(i=1,la=0;i<=n;i=la+1){
41         la = min(n/(n/i),m/(m/i));
42         ret += (long long )(sum[la]-sum[i-1])*(n/i)*(m/i);
43     }
44     return ret;
45 }
46 
47 int main(){
48     int i,j;
49     mobius(50000);
50     for(i=1;i<50000;i++)
51         sum[i] = sum[i-1]+mu[i];
52     scanf("%d",&t);
53     while(t--){
54         scanf("%d%d%d%d%d",&a,&b,&c,&d,&k);
55         long long ans;
56         ans = solve(b/k,d/k)-solve((a-1)/k,d/k)
57             -solve((c-1)/k,b/k)+solve((a-1)/k,(c-1)/k);
58         printf("%lld
",ans);
59     }
60     return 0;
61 }