Description
对于给出的n个询问，每次求有多少个数对(x,y)，满足a≤x≤b，c≤y≤d，且gcd(x,y) = k，gcd(x,y)函数为x和y的最大公约数。
Input Format
第一行一个整数，接下来
行每行五个整数，分别表示
Output Format
共行，每行一个整数表示满足要求的数对
的个数
Sample Input
2
2 5 1 5 1
1 5 1 5 2
Sample Output
14
3
Constraints
对于%的数据，满足
。
CCYOS
关键是一个容斥。
设表示有多少正整数对
，满足
，并且
。(
题中已给出)
经过以下推导：
这是基础
这是ANS(b,d) - ANS(b,c - 1)，记作O
这是ANS(a - 1,d) - ANS(a - 1,c - 1)，记作C
O - C得到所求
余下推导同POI2007 ZAP。
code
#include<bits/stdc++.h>
using namespace std;
#define mxn 60005
int T,a,b,c,d,k,cnt;
int mu[mxn],vis[mxn],prime[mxn],sum[mxn];
inline int read(){
char c = getchar();
int fl = 1,ret = 0;
for(;!isdigit(c)&&c != '-';c = getchar())if(c == '-')fl = 0;
for(;isdigit(c);c = getchar())ret = (ret << 3) + (ret << 1) + c - 48;
return fl ? ret : -ret;
}
inline void get_mu(int n){
mu[1] = 1;
for(int i = 2;i <= n;++i){
if(!vis[i])prime[++cnt] = i,mu[i] = -1;
for(int j = 1;j <= cnt && i * prime[j] <= n;++j){
vis[i * prime[j]] = 1;
if(!(i%prime[j]))break;
else mu[i*prime[j]] = -mu[i];
}
}
for(int i = 1;i <= n;++i)sum[i] = sum[i - 1] + mu[i];
}
inline long long ANS(int N,int M){
int limit = min(M,N);
long long ret = 0;
for(int l = 1,r;l <= limit;l = r + 1){
r = min(N/(N/l),M/(M/l));
ret += 1ll * (N/(l*k)) * (M/(l*k)) * (sum[r] - sum[l - 1]);
}
return ret;
}
int main(){
//freopen("P3455.in","r",stdin);
// freopen("P3345.out","w",stdout);
T = read();
get_mu(50000);
for(int t = 1;t <= T;++t){
a = read();b = read();c = read();d = read();k = read();
long long ans = 0;
ans += ANS(b,d) + ANS(a - 1,c - 1);
ans =ans - ANS(a - 1,d) - ANS(b,c - 1);
printf("%lld\n",ans);
}
return 0;
}
