codevs 5962 [SDOI2017]数字表格

输入描述 Input Description

 [题解]

对于蓝色部分预处理前缀积。

然后在用除法分块搞一下。

O(Q*sqrt(min(n,m))*logn+nlogn)

#include<cstdio>

#include<iostream>

using namespace std;

typedef long long ll;

const int N=1e6+;

const ll mod=1e9+;

int T,n,m,tot,mu[N],prime[N/];bool check[N];

ll f[N],invf[N],g[N];

ll fpow(ll a,ll p){

    ll res=;

    for(;p;p>>=,a=a*a%mod) if(p&) res=res*a%mod;

    return res;

}

void pre(){

    mu[]=;n=1e6;

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

        if(!check[i]) prime[++tot]=i,mu[i]=-;

        for(int j=;j<=tot&&i*prime[j]<=n;j++){

            check[i*prime[j]]=;

            if(!(i%prime[j])){mu[i*prime[j]]=;break;}

            else mu[i*prime[j]]=-mu[i];

        }

    }

    f[]=;

    for(int i=;i<=n;i++) f[i]=(f[i-]+f[i-])%mod;

    for(int i=;i<=n;i++) invf[i]=fpow(f[i],mod-);

    fill(g,g+n+,);

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

        for(int j=;i*j<=n;j++){

            if(mu[j]){

                g[i*j]=g[i*j]*(mu[j]==?f[i]:invf[i])%mod;

            }

        }

    }

    for(int i=;i<=n;i++) g[i]=g[i]*g[i-]%mod;

}

ll solve(int n,int m){

    ll ans=;

    if(n>m) swap(n,m);

    for(int i=,pos;i<=n;i=pos+){

        pos=min(n/(n/i),m/(m/i));

        ans=ans*fpow(g[pos]*fpow(g[i-],mod-)%mod,1LL*(n/i)*(m/i))%mod;

    }

    return ans;

}

int main(){

    pre();

    scanf("%d",&T);

    while(T--) scanf("%d%d",&n,&m),printf("%d\n",(int)solve(n,m));

    return ;

}