[文章目录]
Description
给定n，m，求
n,m<=500000
推式子~不妨设n<=m
枚举gcd
枚举k*d
枚举小d，递推处理1~m/d的d次方和其前缀和，快速幂计算d的d次方，预处理mu，枚举d的倍数D，更新答案。时间复杂度O(nlnn)
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
const ll mod=1000000007;
ll ans[501000],dc[501000],sum[501000],fna;
int n,m,pri[250000],mu[501000],cnt;
bool v[501000];
void quick_mu()
{
mu[1]=1;
for(int i=2;i<=n;++i)
{
if(!v[i]) pri[++cnt]=i,mu[i]=-1;
for(int j=1;i*pri[j]<=n&&j<=cnt;++j)
{
v[i*pri[j]]=1;
if(i%pri[j]) mu[i*pri[j]]=-mu[i];
else {mu[i*pri[j]]=0; break; }
}
}
}
ll Pow(ll x,int y)
{
ll re=1;
while(y)
{
if(y&1) re=re*x%mod;
x=x*x%mod; y>>=1;
}
return re;
}
int main()
{
scanf("%d%d",&n,&m); if(n>m) swap(n,m);
quick_mu(); for(int i=1;i<=m;++i) dc[i]=1;
int d,c,i,k; ll now;
for(d=1;d<=n;++d)
{
c=m/d; now=Pow(d,d);
for(i=1;i<=c;++i) dc[i]=dc[i]*i%mod,sum[i]=(sum[i-1]+dc[i])%mod;
for(k=1;k*d<=n;++k) if(mu[k])
ans[k*d]=(ans[k*d]+now*dc[k]%mod*dc[k]%mod*sum[n/(k*d)]%mod*sum[m/(k*d)]%mod*mu[k]+mod)%mod;
}
for(i=1;i<=n;++i) fna=(fna+ans[i]+mod)%mod;
printf("%lld",fna);
return 0;
}