题目链接
题解
结论与结论的证明参考了rqy的博客
计算(d(ij))时，把ij的每个约数d映射到((a=gcd(d,i),b=(gcd(d,i),frac{d}{gcd(d, i)}))
可知(a,b)分别是(i,j)的因数，且((a,b))对应一个因数当且仅当(gcd(frac ia, b) = 1)，所以
[d(ij) = sum_{x|i}sum_{y|j} [gcd(frac ix, y) = 1] = sum_{x'|i}sum_{y|j} [gcd(x', y) = 1]
]
有了这个式子之后
[sum_{i=1}^nsum_{j=1}^m d(ij) =sum_{i=1}^nsum_{j=1}^msum_{x|i}sum_{y|j} [gcd(x, y) = 1]$$ $$=sum_{i=1}^nsum_{j=1}^m leftlfloorfrac ni
ight
floor leftlfloorfrac mj
ight
floor [gcd(i, j) = 1]$$ $$=sum_{i=1}^{n}sum_{j=1}^{m}sum_{d|i}sum_{d|j}mu(d)lfloorfrac{n}{i}
floorlfloorfrac{m}{j}
floor$$ $$ =sum_{d=1}^{min(n,m)}sum_{i=1}^{lfloorfrac{n}{d}
floor}sum_{j=1}^{lfloorfrac{m}{d}
floor}mu(d)lfloorfrac{n}{i}
floorlfloorfrac{m}{j}
floor $$
]
=sum_{d=1}^{min(n,m)}mu(d)sum_{i=1}^{lfloorfrac{n}{d}
floor}lfloorfrac{n}{i}
floorsum_{j=1}^{lfloorfrac{m}{d}
floor}lfloorfrac{m}{j}
floor$$
用(f(x)=sum_{i=1}^{x}lfloorfrac{x}{i}
floor)表示1-x的约数个数和
[sum_{d=1}^{min(n,m)}mu(d)f(lfloorfrac{n}{d}
floor)f(lfloorfrac{m}{d}
floor)$$预处理$mu(n)$前缀和
对于$f$我们可以$O(nsqrt n)$预处理,查询为$O(sqrt n)$
##代码
```c++
#include<cstdio>
#include<cstring>
#include<algorithm>
const int maxn = 50007;
#define int long long
inline int read() {
int x=0,f=1;
char c=getchar();
while(c<'0'||c>'9'){if(c=='0')f=-1;c=getchar();}
while(c<='9'&&c>='0')x=x*10+c-'0',c=getchar();
return x*f;
}
int f[maxn],mu[maxn],num,prime[maxn];
bool vis[maxn];
inline int countf(int x) {
int ans=0;
for(int i=1,last;i<=x;i=last+1) {
last=x/(x/i);
ans+=x/i*(last-i+1);
}
return ans;
}
void get_mu() {
mu[1]=1;
for(int i=2;i<maxn;++i) {
if(!vis[i])prime[++num]=i,mu[i]=-1;
for(int j=1;j<=num&&i*prime[j]<maxn;++j) {
vis[prime[j]*i]=1;
if(i%prime[j]==0)mu[prime[j]*i]=0;
else mu[i*prime[j]]=-mu[i];
}
}
for(int i=1;i<maxn;++i)mu[i]+=mu[i-1];
}
void init() {
for(int i=1;i<maxn;++i)f[i]=countf(i);
get_mu();
}
int solve(int n,int m) {
int ans=0;
for(int i=1,last;i<=std::min(n,m);i=last+1) {
last=std::min(n/(n/i),m/(m/i));
ans+=(mu[last]-mu[i-1])*f[n/i]*f[m/i];
}
return ans;
}
main() {
init();
int T=read();
for(;T--;) {
printf("%lld
",solve(read(),read()));
}
int tmp=0;
return 0;
}
```]