【题意】给定n,m，求Σlcm(i,j),1<=i<=n,1<=j<=m，n,m<=10^7。
【算法】数论（莫比乌斯反演）
【题解】
$$ans=\sum_{i\leq n}\sum_{j\leq m}\frac{i*j}{gcd(i,j)}$$
$$ans=\sum_{d\leq min(n,m)}1/d\sum_{i\leq n}\sum_{j\leq m}[gcd(i,j)=d]i*j$$
$$ans=\sum_{d\leq min(n,m)}d\sum_{i\leq n/d}\sum_{j\leq m/d}[gcd(i,j)=1]i*j$$
发现后面部分只和n/d，m/d有关，于是封装后分块取值优化。
★$$ans=\sum_{d\leq min(n,m)}d*F(n/d,m/d)$$
$$F(n,m)=\sum_{i\leq n}\sum_{j\leq m}[gcd(i,j)=1]i*j$$
运用e=i*μ反演易得
★$$F(n,m)=\sum_{d\leq min(n,m)}\mu (d)*d^2*sum(n/d,m/d)$$
$$sum(n,m)=\sum_{i\leq n}\sum_{j\leq m}i*j=\sum_{i\leq n}i\sum_{j\leq m}j$$
★$$sum(n,m)=\frac{n(n+1)}{2}*\frac{m(m+1)}{2}$$
（这步由一般分配律）
最后就是两次分块取值优化，√n*√n，复杂度O(n)。
#include<cstdio>
#include<algorithm>
using namespace std;
const int maxn=,MOD=;
int sum[maxn],n,m,miu[maxn],prime[maxn],tot;
bool mark[maxn];
int M(int x){return x>=MOD?x-MOD:x;}
int SUM(int x,int y){return 1ll*x*(x+)/%MOD*(1ll*y*(y+)/%MOD)%MOD;}
int solve(int x,int y){
int z=min(x,y),ans=,pos=;
for(int i=;i<=z;i=pos+){
pos=min(x/(x/i),y/(y/i));
ans=(ans+1ll*(sum[pos]-sum[i-])*SUM(x/i,y/i)%MOD)%MOD;
}
return ans;
}
int main(){
scanf("%d%d",&n,&m);
int z=min(n,m);
miu[]=sum[]=;
for(int i=;i<=z;i++){
if(!mark[i])miu[prime[++tot]=i]=-;
for(int j=;j<=tot&&i*prime[j]<=z;j++){
mark[i*prime[j]]=;
if(i%prime[j]==)break;
miu[i*prime[j]]=-miu[i];
}
sum[i]=(sum[i-]+1ll*i*i*miu[i]%MOD)%MOD;
}
int pos=,ans=;
for(int i=;i<=z;i=pos+){
pos=min(n/(n/i),m/(m/i));
ans=(ans+1ll*(pos+i)*(pos-i+)/%MOD*solve(n/i,m/i))%MOD;
}
printf("%d",(ans+MOD)%MOD);
return ;
}