Description
设 (d(x)) 为 (x) 的约数个数，给定 (N) 、(M)，求 (sumlimits_{i=1}^N sumlimits_{j=1}^M d(ij))
Input
输入文件包含多组测试数据。
第一行，一个整数 (T) ，表示测试数据的组数。
接下来的 (T) 行，每行两个整数 (N) 、(M) 。
Output
(T) 行，每行一个整数，表示你所求的答案。
Sample Input
2
7 4
5 6
Sample Output
110
121
HINT
(1<=N, M<=50000)
(1<=T<=50000)
想法
首先有一个结论
$ d(i,j)=sumlimits_{x|i} sumlimits_{y|j} [gcd(x,y)==1] $
原谅我不会证 (qwq)
接下来，喜闻乐见的推式子
[egin{equation*}
egin{aligned}
&sumlimits_{i=1}^n sumlimits_{j=1}^m d(ij) \
=&sumlimits_{i=1}^n sumlimits_{j=1}^m sumlimits_{x|i} sumlimits_{y|j} [gcd(x,y)==1] \
=&sumlimits_{i=1}^n sumlimits_{j=1}^m [gcd(x,y)==1] imes lfloor frac{n}{x}
floor imes lfloor frac{m}{y}
floor \
end{aligned}
end{equation*}
]
设 (f(i)=sumlimits_{i=1}^n sumlimits_{j=1}^m [gcd(x,y)==1] imes lfloor frac{n}{x}
floor imes lfloor frac{m}{y}
floor)
应用莫比乌斯反演
[egin{equation*}
egin{aligned}
F(i)&=f(i)+f(2i)+... \
&=sumlimits_{x=1}^{lfloor frac{n}{i}
floor} sumlimits_{y=1}^{lfloor frac{m}{i}
floor} lfloor frac{n}{ix}
floor lfloor frac{m}{iy}
floor \
&=sumlimits_{x=1}^{lfloor frac{n}{i}
floor} lfloor frac{n}{ix}
floor sumlimits_{y=1}^{lfloor frac{m}{i}
floor} lfloor frac{m}{iy}
floor
end{aligned}
end{equation*}
]
不妨设 (s(x)=sumlimits_{i=1}^x lfloor frac{x}{i}
floor)
它可以预处理后 (O(1)) 调用
则 (f(i)=sumlimits_{i|d} mu(frac{d}{i}) s(frac{n}{d}) s(frac{m}{d}))
那么
[egin{equation*}
egin{aligned}
ans&=f(1) \
&=sumlimits_{i=1}^{min(n,m)} mu(i) s(frac{n}{i})s(frac{m}{i})
end{aligned}
end{equation*}
]
然后就好啦。
代码
#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 50005;
typedef long long ll;
ll s[N];
int mu[N],p[N],prime[N],pnum,sum[N];
void getp(){
mu[1]=sum[1]=1;
for(int i=2;i<N;i++) p[i]=1;
for(int i=2;i<N;i++){
if(p[i]) prime[pnum++]=i,mu[i]=-1;
for(int j=0;j<pnum && (ll)prime[j]*i<N;j++){
p[i*prime[j]]=0;
if(i%prime[j]==0){
mu[i*prime[j]]=0;
break;
}
mu[i*prime[j]]=-mu[i];
}
sum[i]=sum[i-1]+mu[i];
}
}
void gets(){
for(int x=1;x<N;x++){
for(int l=1,r;l<=x;l=r+1){
r=x/(x/l);
s[x]+=1ll*(x/l)*(r-l+1);
}
}
}
int main()
{
int T,n,m;
getp(); gets();
scanf("%d",&T);
while(T--){
scanf("%d%d",&n,&m);
ll ans=0;
for(int l=1,r;l<=n && l<=m;l=r+1){
r=min(n/(n/l),m/(m/l));
ans+=s[n/l]*s[m/l]*(sum[r]-sum[l-1]);
}
printf("%lld
",ans);
}
return 0;
}