【反演复习计划】【bzoj4407】于神之怒加强版

#include<bits/stdc++.h>

#define N 5000010

#define yql 1000000007

using namespace std;

typedef long long ll;

int T,k,n[],m[],maxn,vis[N],prime[N];

int mu[N],cnt=,fac[N];

ll f[N],s[N];

inline int read(){

    int f=,x=;char ch;

    do{ch=getchar();if(ch=='-')f=-;}while(ch<''||ch>'');

    do{x=x*+ch-'';ch=getchar();}while(ch>=''&&ch<='');

    return f*x;

}

inline ll fpow(ll x,ll p){

    x%=yql;ll ans=;

    for(;p;p>>=,x=x*x%yql)if(p&)ans*=x,ans%=yql;

    return (ans+yql)%yql;

}

void calcmu(){

    cnt=;mu[]=;s[]=;memset(vis,,sizeof(vis));

    for(int i=;i<=maxn;i++){

        if(vis[i]){prime[++cnt]=i;fac[i]=i;mu[i]=-;f[i]=fpow(i,k);s[i]=f[i]-;}

        for(int j=;j<=cnt;j++){

            int p=prime[j],t=i*p;if(t>maxn)break;

            vis[t]=;

            if(i%p==){

                mu[t]=;fac[t]=fac[i]*p;

                s[t]=1LL*s[i]*f[prime[j]]%yql;

                break;

            }

            mu[t]=-mu[i];s[t]=1LL*s[i]*s[p]%yql;

        }

    }

    for(int i=;i<=maxn;i++)mu[i]+=mu[i-],s[i]+=s[i-],s[i]%=yql;

}

int main(){

    T=read();k=read();

    for(int i=;i<=T;i++){

        n[i]=read(),m[i]=read();

        maxn=max(maxn,max(n[i],m[i]));

    }

    calcmu();

    for(int i=;i<=T;i++){

        int nn=n[i],mm=m[i];if(nn>mm)swap(nn,mm);

        ll ans=;

        for(int i=,j=;i<=nn;i=j+){

            j=min(mm/(mm/i),nn/(nn/i));

            ans+=(s[j]-s[i-]+yql)%yql*(nn/i)%yql*(mm/i)%yql;ans%=yql;

        }

        printf("%lld\n",ans);

    }

}

试了下maxn操作，结果还是BZOJ倒数TAT

感觉式子化得没问题啊？