莫比乌斯反演
对于这种题目，显然是一个数学题，因此可以转换。
不妨钦定 $n\leq m$，否则交换 $n,m$。
记答案为 $\textit{ans}$：
\[\begin{aligned} \textit{ans}&=\sum_{i=1}^n\sum_{j=1}^m\operatorname{lcm}(i,j)\\ &=\sum_{i=1}^n\sum_{j=1}^m\dfrac{ij}{\gcd(i,j)}\\ &=\sum_{d=1}^n\sum_{i=1}^n\sum_{j=1}^m[\gcd(i,j)=d]\frac{ij}{d}\\ \end{aligned}\]将枚举的 $i,j$ 换为 $i’d,j’d$，则 $i’\perp j’$：
\[\textit{ans}=\sum_{d=1}^nd\sum_{i=1}^{\large\left\lfloor\frac nd\right\rfloor}\sum_{j=1}^{\large\left\lfloor\frac md\right\rfloor}[i\perp j]ij\]考虑到：
\[[i\perp j]=[\gcd(i,j)=1]=\sum_{d\mid\gcd(i,j)}\mu(d)=\sum_{d\mid i\land d\mid j}\mu(d)\]因此：
\[\textit{ans}=\sum_{d=1}^nd\sum_{i=1}^{\large\left\lfloor\frac nd\right\rfloor}\sum_{j=1}^{\large\left\lfloor\frac md\right\rfloor}\sum_{k\mid\gcd(i,j)}\mu(k)ij\]我们可以枚举 $k$。因为 $k\mid\gcd(i,j)$，$i,j$ 的上界为 $\left\lfloor\dfrac nd\right\rfloor$，因此从 $1\sim\left\lfloor\dfrac nd\right\rfloor$ 枚举。
\[\textit{ans}=\sum_{d=1}^nd\sum_{k=1}^{\large\left\lfloor\frac nd\right\rfloor}\mu(k)\sum_{i=1}^{\large\left\lfloor\frac nd\right\rfloor}\sum_{j=1}^{\large\left\lfloor\frac md\right\rfloor}[k\mid\gcd(i,j)]ij\]$k\mid\gcd(i,j)$ 即 $k\mid i\land k\mid j$，因此可以枚举 $i=i’l,j=j’k$：
\[\begin{aligned} \textit{ans}&=\sum_{d=1}^nd\sum_{k=1}^{\large\left\lfloor\frac nd\right\rfloor}\mu(k)k^2\sum_{i=1}^{\large\left\lfloor\frac n{kd}\right\rfloor}\sum_{j=1}^{\large\left\lfloor\frac m{kd}\right\rfloor}ij\\ &=\sum_{d=1}^nd\sum_{k=1}^{\large\left\lfloor\frac nd\right\rfloor}\mu(k)k^2\left(\sum_{i=1}^{\large\left\lfloor\frac n{kd}\right\rfloor}i\right)\left(\sum_{j=1}^{\large\left\lfloor\frac m{kd}\right\rfloor}j\right) \end{aligned}\]枚举 $d$ 是 $\mathcal O(n)$ 的，考虑快速求出后半部分。
若 $k,d$ 确定，则可以由等差数列求和快速求出 $\sum_{i=1}\limits^{\large\left\lfloor\frac n{kd}\right\rfloor}i,\sum_{j=1}\limits^{\large\left\lfloor\frac n{kd}\right\rfloor}j$。
可以考虑进行数论分块，则 $k$ 在一段区间 $[l,r]$ 内，$\left\lfloor\dfrac n{kd}\right\rfloor$ 均相同，$\left\lfloor\dfrac n{kd}\right\rfloor$ 均相同。于是后两项就可以确定。对于 $\mu(k)k^2$，线性筛后维护一个前缀和即可。
AC 代码
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
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
//#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;
#define int long long
constexpr const int N=1e7,P=20101009,inv4=15075757;
int preU[N+1];
void pre(){
static int vis[N+1],prime[N+1],size;
preU[1]=1;
for(int i=2;i<=N;i++){
if(!vis[i]){
prime[++size]=i;
vis[i]=i;
preU[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;
}
preU[i*prime[j]]=-preU[i];
}
}
for(int i=1;i<=N;i++){
preU[i]=1ll*preU[i]*i*i%P;
preU[i]+=preU[i-1];
preU[i]%=P;
}
}
ll f(int n,int m){
if(n>m){
swap(n,m);
}
// for(int i=1;i<=n;i++){
// cerr<<"u["<<i<<"]="<<preU[i]-preU[i-1]-i*i<<endl;
// cerr<<"u["<<i<<"]+"<<i<<"^2="<<preU[i]-preU[i-1]<<endl;
// cerr<<"preU["<<i<<"]="<<preU[i]<<endl;
// }
int ans=0;
for(int d=1;d<=n;d++){
int n2=n/d,m2=m/d;
// cerr<<"-------------------------------\nd="<<d<<":\n";
// cerr<<"floor(n/d)="<<n2<<" floor(m/d)="<<m2<<endl;
int ans2=ans;
for(int l=1,r=n2;l<=n2;l=r+1,r=n2){
int tn=n2/l,tm=m2/l;
// cerr<<"tn="<<tn<<" tm="<<tm<<endl;
r=min(n2/tn,m2/tm);
// cerr<<"["<<l<<","<<r<<"]\n";
// cerr<<"preU[r]="<<preU[r]<<" preU[l-1]="<<preU[l-1]<<endl;
// cerr<<"add = "<<1ll*d*(preU[r]-preU[l-1])*inv4%P*tn*(tn+1)%P*tm*(tm+1)%P<<endl;
ans+=1ll*d*(preU[r]-preU[l-1])%P*inv4%P*tn%P*(tn+1)%P*tm%P*(tm+1)%P;
ans%=P;
}
// cerr<<ans-ans2<<endl;
// int add=0;
// for(int k=1;k*d<=n;k++){
// int nn=n/k/d,mm=m/k/d;
// add+=1ll*d*(preU[k]-preU[k-1]-k*k)/*u[k]*/*k%P*k%P*(1+nn)*nn%P%P*(1+mm)*mm%P*inv4%P;
// add%=P;
// }
// cout<<"add in all should be "<<add<<endl;
}
if(ans<0){
ans+=P;
}
return ans;
}
main(){
/*freopen("test.in","r",stdin);
freopen("test.out","w",stdout);*/
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
pre();
int n,m;
cin>>n>>m;
cout<<f(n,m)<<'\n';
cout.flush();
/*fclose(stdin);
fclose(stdout);*/
return 0;
}
