一看到love math就知道肯定不会做。。
首先lcm拆成i*j/gcd(i,j),然后就讨论分子和分母。。但并没有什么卵用
这个题对比传统反演题,主要不同的是f函数不是很直观。。
所以如果枚举gcd,那剩下的两个数一定互质,然后就按照gcd==1的反演直接套在后面,不同的是原来的[m/d] 和 [n/d] 换成新的函数 Σi^dΣj^d
所以式子是:
![](https://img-blog.csdn.net/20171009075815331?watermark/2/text/aHR0cDovL2Jsb2cuY3Nkbi5uZXQvaGFvYmFuZzg2Ng==/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70/gravity/Center)
运用调和级数nlogn
码;
#include<iostream>
#include<cstdio>
using namespace std;
#define ll long long
#define P 1000000007
ll mu[500005],su[500005],he[500005],ci[500005],tot,i,j,n,m,ans,T;
bool hs[500005];
void eular(ll n)
{
int i,j;mu[1]=1;
for(i=2;i<=n;i++)
{
if(!hs[i])
{
su[++tot]=i;
mu[i]=-1;
}
for(j=1;j<=tot&&i*su[j]<=n;j++)
{
hs[su[j]*i]=1;
if((i%su[j])==0)
{
mu[i*su[j]]=0;
break;
} else mu[i*su[j]]=-mu[i];
}
}
}
ll ksm(ll a,ll b)
{
ll ans=1;
while(b)
{
if(b%2)ans=(ans*a)%P;
b/=2;
a=(a*a)%P;
}
return ans;
}
int main()
{
scanf("%lld%lld",&n,&m);
if(n>m)swap(n,m);
eular(n);
for(i=1;i<=m;i++)ci[i]=1;
for(i=1;i<=n;i++)
{
ll lin=ksm(i,i),lin2=0;
for(j=1;j*i<=m;j++)
{
ci[j]=(ci[j]*j)%P;
he[j]=(he[j-1]+ci[j])%P;
}
for(j=1;j*i<=n;j++)
{if(!mu[j])continue;
lin2=(mu[j]*he[m/i/j]%P*he[n/i/j]%P*ci[j]%P*ci[j]%P+lin2+P)%P;
}
ans=(ans+lin*lin2%P)%P;
}
printf("%lld",(ans+P)%P);
}