题链：
http://www.lydsy.com/JudgeOnline/problem.php?id=3561
题解：
莫比乌斯反演
$$egin{aligned}
ANS&=sum_{i=1}^{n}sum_{j=1}^{m}lcm(i,j)^{gcd(i,j)}\
&=sum_{g=1}^{min(n,m)}sum_{i=1}^{frac{n}{g}}sum_{j=1}^{frac{m}{g}}g^gi^gj^g[gcd(i,j)==1]\
&=sum_{g=1}^{min(n,m)}g^gsum_{i=1}^{frac{n}{g}}sum_{j=1}^{frac{m}{g}}i^gj^gsum_{d|gcd(i,j)}mu(d)\
&=sum_{g=1}^{min(n,m)}g^gsum_{d=1}^{min(frac{n}{g},frac{m}{g})}mu(d) sum_{i=1}^{frac{n}{gd}}(id)^gsum_{j=1}^{frac{m}{gd}}(jd)^g\
&=sum_{g=1}^{min(n,m)}g^gsum_{d=1}^{min(frac{n}{g},frac{m}{g})}mu(d) imes d^{2g} sum_{i=1}^{frac{n}{gd}}i^gsum_{j=1}^{frac{m}{gd}}j^g\
end{aligned}$$
上面这个式子直接$O(NlogN)$计算就好了。
代码：
#include<bits/stdc++.h>
#define MAXN 500050
using namespace std;
const int mod=1000000007;
int mu[MAXN],mi[MAXN],smi[MAXN];
int Pow(int a,int b){
int ret=1;
while(b){
if(b&1) ret=1ll*ret*a%mod;
b>>=1; a=1ll*a*a%mod;
}
return ret;
}
void Sieve(){
static bool np[MAXN];
static int prime[MAXN],pnt;
mu[1]=1;
for(int i=2;i<=500000;i++){
if(!np[i]) prime[++pnt]=i,mu[i]=-1;
for(int j=1;j<=pnt&&i<=500000/prime[j];j++){
np[i*prime[j]]=1;
if(i%prime[j]) mu[i*prime[j]]=-mu[i];
else break;
}
}
}
int main(){
Sieve();
int n,m,ans=0; scanf("%d%d",&n,&m);
if(n>m) swap(n,m);
for(int i=1;i<=500000;i++) mi[i]=1;
for(int g=1,gg;g<=n;g++){
gg=Pow(g,g);
for(int i=1;i<=m/g;i++)
mi[i]=1ll*mi[i]*i%mod,smi[i]=(1ll*smi[i-1]+mi[i])%mod;
for(int d=1;d<=n/g;d++)
ans=(1ll*ans+1ll*mu[d]*mi[d]%mod*mi[d]%mod*smi[n/(g*d)]%mod*smi[m/(g*d)]%mod*gg%mod)%mod;
}
printf("%d",ans);
return 0;
}