简要题意
\(T\) 组数据，每组数据给出 \(n,m\)，计算：
\[\sum_{i=1}^{n}\sum_{j=1}^{m}\sum_{d\mid ij}{1} \]\(1 \leq T,n,m \leq 5 \times 10^4\)
思路
又是推式子好题，不过这一次需要莫比乌斯反演了。
\[\begin{aligned} &\textbf{下设 }n<m\\ &\because\sum_{d\mid ij}{1}=\sum_{x\mid i}\sum_{y\mid j}{[\gcd(x,y)=1]}\\ &\therefore\textbf{原式}=\sum_{i=1}^{n}\sum_{j=1}^{m}\sum_{d\mid ij}{\sum_{x\mid i}\sum_{y\mid j}{[\gcd(x,y)=1]}}\\ &=\sum_{x=1}^{n}\sum_{y=1}^{m}{\lfloor\dfrac{n}{x}\rfloor\lfloor\dfrac{m}{y}\rfloor[\gcd(x,y)=1]}\\ &\textbf{设原式为}{f(x)}\text{, }g(x)=\sum_{x\mid d}{f(d)}\\ &\textbf{则 }g(x)=\sum_{i=1}^{\lfloor n\div x\rfloor}\sum_{j=1}^{\lfloor m\div x\rfloor}\lfloor\dfrac{n}{ix}\rfloor\lfloor\dfrac{m}{jx}\rfloor\\ &\textbf{答案为} f(1)\\ &\textbf{根据莫比乌斯定理得 }f(1)=\sum_{i=1}^{n}{\mu(i)g(i)}\\ \end{aligned} \]最后再用数论分块计算出 \(g\) 函数即可。
时间复杂度 \(O(Tn\sqrt{n})\)。
代码
#include <bits/stdc++.h>
#define int long long
using namespace std;
int mu[10000005],vis[10000005],prime[10000005],qzh[10000005],tot;
int fk[10000005];
void sieve(){
mu[1]=1;
for(int i=2;i<=5e4;i++){
if(!vis[i]){
prime[++tot]=i;
mu[i]=-1;
}
for(int j=1;j<=tot&&i*prime[j]<=5e4;j++){
vis[i*prime[j]]=1;
if(!(i%prime[j])){
break;
}
mu[i*prime[j]]-=mu[i];
}
}
for(int i=1;i<=5e4;i++)qzh[i]=qzh[i-1]+mu[i];
for(int x=1;x<=5e4;x++){
int res=0;
for(int i=1,j;i<=x;i=j+1){
j=x/(x/i);
res+=(j-i+1)*(x/i);
}
fk[x]=res;
}
}
signed main(){
sieve();
int t;cin>>t;
while(t--){
int n,m;
cin>>n>>m;
if(n>m)swap(n,m);
int ans=0;
for(int i=1,j;i<=n;i=j+1){
j=min(n/(n/i),m/(m/i));
ans+=(qzh[j]-qzh[i-1])*fk[n/i]*fk[m/i];
}
cout<<ans<<'\n';
}
return 0;
}