题意分析
不妨令 $n\leq m$。
首先，答案为：
\[\sum_{i=1}^n\sum_{j=1}^md(ij)\]这个 $d(ij)$ 表示 $ij$ 的约数个数，很不好处理。
因此可以考虑 $d(ij)$ 能否化简，有：
\[d(ij)=\sum_{x\mid i}\sum_{y\mid i}[x\perp y]\]证明参见此处。
因此可以进行推导。记答案为 $\textit{ans}$
\(\begin{aligned} \textit{ans}&=\sum_{i=1}^n\sum_{j=1}^m\sum_{x\mid i}\sum_{y\mid i}[x\perp y]\\ &=\sum_{x=1}^n\sum_{y=1}^m[x\perp y]\sum_{i=1}^{\left\lfloor\frac nx\right\rfloor}\sum_{j=1}^{\left\lfloor\frac my\right\rfloor}1\\ &=\sum_{x=1}^n\sum_{y=1}^m[x\perp y]\left\lfloor\frac nx\right\rfloor\left\lfloor\frac my\right\rfloor\\ &=\sum_{x=1}^n\sum_{y=1}^m\sum_{t\mid\gcd(x,y)}\mu(t)\left\lfloor\frac nx\right\rfloor\left\lfloor\frac my\right\rfloor\\ &=\sum_{t=1}^n\mu(t)\sum_{x=1}^{\left\lfloor\frac nt\right\rfloor}\sum_{y=1}^{\left\lfloor\frac mt\right\rfloor}\left\lfloor\frac n{xt}\right\rfloor\left\lfloor\frac m{yt}\right\rfloor\\ &=\sum_{t=1}^n\mu(t)\left(\sum_{x=1}^{\left\lfloor\frac nt\right\rfloor}\left\lfloor\frac n{xt}\right\rfloor\right)\left(\sum_{y=1}^{\left\lfloor\frac mt\right\rfloor}\left\lfloor\frac m{yt}\right\rfloor\right) \end{aligned}\) 预处理 $\displaystyle s_i=\sum_{x=1}^i\left\lfloor\frac ni\right\rfloor$ 即可利用数论分块 $\mathcal O(\sqrt n)$ 计算。
AC 代码
时间复杂度：$\mathcal O(T\sqrt n)$。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
//#include<bits/stdc++.h>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<iomanip>
#include<cstdio>
#include<string>
#include<vector>
#include<cmath>
#include<ctime>
#include<deque>
#include<queue>
#include<stack>
#include<list>
using namespace std;
typedef long long ll;
constexpr const int N=50000;
int mu[N+1];
ll s[N+1];
void pre(){
static int vis[N+1],prime[N+1],size;
mu[1]=1;
for(int i=2;i<=N;i++){
if(!vis[i]){
vis[i]=i;
prime[++size]=i;
mu[i]=-1;
}
for(int j=1;j<=size&&i*prime[j]<=N;j++){
vis[i*prime[j]]=prime[j];
if(i%prime[j]==0){
break;
}
mu[i*prime[j]]=-mu[i];
}
}
for(int i=1;i<=N;i++){
mu[i]+=mu[i-1];
}
for(int i=1;i<=N;i++){
for(int l=1,r;l<=i;l=r+1){
int ti=i/l;
r=i/ti;
s[i]+=(r-l+1ll)*ti;
}
}
}
int main(){
/*freopen("test.in","r",stdin);
freopen("test.out","w",stdout);*/
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
pre();
int T;
cin>>T;
while(T--){
int n,m;
cin>>n>>m;
if(m>n){
swap(n,m);
}
ll ans=0;
for(int l=1,r;l<=m;l=r+1){
int tn=n/l,tm=m/l;
r=min(n/tn,m/tm);
ans+=(mu[r]-mu[l-1])*s[tn]*s[tm];
}
cout<<ans<<'\n';
}
cout.flush();
/*fclose(stdin);
fclose(stdout);*/
return 0;
}
