简要题意
\(n\) 组数据，每组数据给定 \(a,b,c,d,k\)，计算：
\[\sum_{i=a}^{b}\sum_{j=c}^{d}{[\gcd(i,j)=k]} \]\(a\leq b,c\leq d,1\leq n,a,b,c,d,k\leq5\times10^4\)。时间限制 \(2.5\operatorname{s}\)。
简要题意
莫比乌斯反演基础练习题。
首先容斥，令 \(f(x,y)=\sum_{i=1}^{x}\sum_{j=1}^{y}[\gcd(i,j)=k]\)。则原式化为：
\[f(b,d)-f(a-1,d)-f(b,c-1)+f(a-1,c-1) \]考虑化简 \(f\)。
先将 \(i,j\) 同时约去 \(k\)，得：
\[\sum_{i=1}^{\lfloor\frac{x}{k}\rfloor}\sum_{j=1}^{\lfloor\frac{y}{k}\rfloor}[\gcd(i,j)=1] \]根据莫比乌斯函数性质：\(\sum_{d\mid x}{\mu(d)}=[x=1]\) 得：
\[\sum_{i=1}^{\lfloor\frac{x}{k}\rfloor}\sum_{j=1}^{\lfloor\frac{y}{k}\rfloor}\sum_{d\mid\gcd(i,j)}{\mu(d)} \]将第三个 \(\sum\) 的下限变形得：
\[\sum_{i=1}^{\lfloor\frac{x}{k}\rfloor}\sum_{j=1}^{\lfloor\frac{y}{k}\rfloor}\sum_{d\mid i,d\mid j}{\mu(d)} \]将 \(d\) 提到前面去，得：
\[\sum_{d=1}^{\min(x,y)}\mu(d)\sum_{i=1}^{\lfloor\frac{x}{k}\rfloor}\sum_{j=1}^{\lfloor\frac{y}{k}\rfloor}[d\mid i][d\mid j] \]将右边得两个 \(\sum\) 化简，得：
\[\sum_{d=1}^{\min(x,y)}\mu(d)\lfloor\frac{x}{dk}\rfloor\lfloor\frac{y}{dk}\rfloor \]数论分块做即可。
时间复杂度 \(O(\max(b,d)+T\sqrt{\min(b,d)})\)。
注意，不要 #define int long long！
代码
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5+5;
int mu[N],prime[N],tot;
long long sum[N];
bool vis[N];
int a,b,c,d,k,t;
inline void sieve(int bound){
mu[1]=1;vis[1]=1;
for(int i=2;i<=bound;i++){
if(!vis[i]){
prime[++tot]=i;
mu[i]=-1;
}
for(int j=1;j<=tot&&i*prime[j]<=bound;j++){
vis[i*prime[j]]=1;
if(i%prime[j]) mu[i*prime[j]]=-mu[i];
else{
mu[i*prime[j]]=0;
break;
}
}
}
for(int i=1;i<=bound;i++){
sum[i]=sum[i-1]+mu[i];
}
}
long long solve(int x,int y){
long long ret=0;
for(int i=1,j;i<=min(x,y);i=j+1){
j=min(x/(x/i),y/(y/i));
ret+=(1ll*x/(1ll*i*k))*1ll*(1ll*y/(1ll*i*k))*(sum[j]-sum[i-1]);
}
return ret;
}
signed main(){
ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
sieve(5e4);
cin>>t;
while(t--){
cin>>a>>b>>c>>d>>k;
cout<<(solve(b,d)-solve(a-1,d)-solve(b,c-1)+solve(a-1,c-1))<<'\n';
}
return 0;
}