BZOJ-3561: DZY Loves Math VI

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;
}