题意:求sigma{lcm(i,j)},1<=i<=n,1<=j<=m
不妨令n<=m
首先把lcm(i,j)转成i*j/gcd(i,j)
正解不会...总之最后化出来的莫比乌斯反演式子并没有除法…
本脑子有坑选手的做法：20101009是一个质数,而且n和m的范围小于20101009,这一定有其原因。经过仔细思考,我们发现这保证了每个1~n的数都有mod20101009意义下的乘法逆元。用inv[x]表示x的逆元,我们发现原先的式子等于sigma{inv[gcd(i,j)]*i*j},1<=i<=n,1<=j<=m
于是我们枚举g=gcd(i,j)则原式等于sigma{inv[g]*H(g)},1<=g<=n
H(g)=sigma{i*j},1<=i<=n,1<=j<=m,gcd(i,j)==g.
定义h(g)= sigma{i*j},1<=i<=n,1<=j<=m,g|gcd(i,j),我们发现，h(g)可以方便地求出,且h(g)是H(g)的倍数和,这启发我们使用莫比乌斯反演,H(g)=sigma{mu(q/g)*h(q)},g|q,1<=q<=n接下来我们将式子变形为先枚举q,则原式=sigma{h(q)*sigma{inv[g]*mu(q/g),g|q}}1<=q<=n
我们知道莫比乌斯函数和乘法逆元都是积性函数，积性函数的积，积性函数的约数和也是积性函数，这启发我们用线性筛预处理G(q)=sigma{inv[g]*mu(q/g),g|q}!接下来暴力枚举q即可。
而1-n所有数的逆元也有线性的方法可以求出,
综上，我们得到了一个时空复杂度均为O(n)的优越算法(大雾)。
然而常数大,T得飞起….
#include<cstdio>
#include<ctime>
#include<algorithm>
using namespace std;
typedef long long ll;
const int maxn=;const ll mod=;
int niyuan[maxn];
bool flag[maxn];
int prime[maxn/],mu[maxn],f[maxn],h[maxn],g[maxn],tot;
void linear(){
niyuan[]=;f[]=;
// for(int i=2;i<maxn;++i)niyuan[i]=niyuan[mod%i]*niyuan[mod%i]%mod*(mod/i)%mod*(mod/i)%mod*i%mod;//常数已炸天,0.6s+
int tmp;
for(int i=,last;i<maxn;i=last+){
last=mod/(mod/i);
tmp=mod/i;tmp=tmp*1LL*tmp%mod;
for(int j=i;j<=last&&j<maxn;++j)niyuan[j]=niyuan[mod%j]*1LL*niyuan[mod%j]%mod*tmp*j%mod;
}
mu[]=;
for(int i=;i<maxn;++i){
if(!flag[i]){
prime[++tot]=i;mu[i]=-;
f[i]=mu[i]+niyuan[i];h[i]=i;g[i]=;
}
for(int j=;j<=tot&&prime[j]*i<maxn;++j){
tmp=i*prime[j];
flag[tmp]=true;
if(i%prime[j]==){
mu[tmp]=;
g[tmp]=g[i];
h[tmp]=h[i]*1LL*prime[j]%mod;
f[tmp]=f[g[i]]*1LL*(niyuan[h[i]*1LL*prime[j]%mod]-niyuan[h[i]]+mod)%mod;
break;
}else{
mu[tmp]=-mu[i];
h[tmp]=prime[j];
g[tmp]=i;
f[tmp]=f[i]*1LL*f[prime[j]]%mod;
}
}
}
}
int n,m;
ll f2(ll x){
ll a=n/x,b=m/x;
return a*(a+)%mod*b%mod*(b+)%mod*niyuan[]%mod*x*x%mod;
}
int solve(){
if(n>m)swap(n,m);
int ans=;
for(int d=;d<=n;++d){
ans=ans+f2(d)*f[d]%mod;ans%=mod;
}
return ans;
}
int main(){
linear();
scanf("%d%d",&n,&m);
printf("%d\n",solve());
return ;
}
UPD:线性筛改成筛到min(n,m)而不是筛到maxn，因为小数据比较多,按总时限在bzoj卡过去了,感人肺腑(虽然极限数据的单点时限还是会T)
(有个数组开longlong结果MLE了)