所谓莫比乌斯反演，就是把好看的式子变得越来越猥琐（题外话）
开始变形：
[sumlimits_{i=1}^nsumlimits_{j=1}^mlca(i,j)
]
[=sumlimits_{i=1}^nsumlimits_{j=1}^mfrac{ij}{gcd(i,j)}
]
[=sumlimits_{d=1}^nfrac1dsumlimits_{i=1}^{left[frac nd
ight]}sumlimits_{j=1}^{left[frac md
ight]}ijd^2*[gcd(i,j)=1]
]
[=sumlimits_{d=1}^ndsumlimits_{i=1}^{left[frac nd
ight]}sumlimits_{j=1}^{left[frac md
ight]}ijsumlimits_{k|gcd(i,j)}mu(k)
]
[=sumlimits_{d=1}^ndsumlimits_{k=1}^{left[frac nd
ight]}mu(k)k^2sumlimits_{i=1}^{left[frac {n}{dk}
ight]}sumlimits_{j=1}^{left[frac {m}{dk}
ight]}ij
]
[=sumlimits_{d=1}^ndsumlimits_{k=1}^{left[frac nd
ight]}mu(k)k^2frac14left[frac {n}{dk}
ight]left(left[frac {n}{dk}
ight]+1
ight)left[frac {m}{dk}
ight]left(left[frac {m}{dk}
ight]+1
ight)
]
这时使出我们的必杀技：令(t=dk)
[frac14sumlimits_{t=1}^nleft[frac {n}{t}
ight]left(left[frac {n}{t}
ight]+1
ight)left[frac {m}{t}
ight]left(left[frac {m}{t}
ight]+1
ight)sumlimits_{d|t}mu(d)d^2frac td
]
[=frac14sumlimits_{t=1}^nleft[frac {n}{t}
ight]left(left[frac {n}{t}
ight]+1
ight)left[frac {m}{t}
ight]left(left[frac {m}{t}
ight]+1
ight)sumlimits_{d|t}mu(d)dt
]
对于每一个(t)，(sumlimits_{d|t}mu(d)dt)可以预处理，其余分块即可。
附上代码，放心食用：
#include<bits/stdc++.h>
#define int long long
const int maxn=1e7;
const int mod=20101009;
int mu[maxn+10],h[maxn+10],pri[maxn/100],tot;
int n,m;
inline void init(){
mu[1]=1;
for(int i=2;i<=n;i++){
if(!h[i])mu[i]=-1,pri[++tot]=i;
for(int j=1;j<=tot&&pri[j]*i<=n;j++){
h[pri[j]*i]=1;
if(i%pri[j]==0)break;
mu[pri[j]*i]=-mu[i];
}
}
memset(h,0,sizeof(h));
for(int i=1;i<=n;i++)
if(mu[i]!=0)
for(int j=1;j<=n/i;j++)
h[i*j]=(h[i*j]+mu[i]*i)%mod;
for(int i=1;i<=n;i++)
h[i]=(i*h[i]+h[i-1])%mod;
}
signed main(){
scanf("%lld%lld",&n,&m);
if(n>m)std::swap(n,m);
init();
int ans=0;
for(int l=1,r;l<=n;l=r+1){
r=std::min(n/(n/l),m/(m/l));
ans=(ans+((((n/l)*(n/l+1)/2)%mod)*(((m/l)*(m/l+1)/2)%mod)%mod*(h[r]-h[l-1])%mod))%mod;
}
printf("%lld
",(ans%mod+mod)%mod);
return 0;
}
深深地感到自己的弱小。