大力推式子

现根据套路枚举\(\gcd(i,j)\)

\(ans=\Pi_{x=1}^nfib[x]^{\sum_{i=1}^{n/x}\sum_{j=1}^{n/x}[\gcd(i,j)=1]}\)

莫比乌斯反演

\(ans=\Pi_{x=1}^nfib[x]^{\sum_{i=1}^{n/x}\mu(i)(n/ix)(m/ix)}\)

把枚举\(i\)提出来，改成枚举\(ix\)，里面还是枚举\(x\)

\(ans=\Pi_{i=1}^n\Pi_{x|i}fib[x]^{\mu(i/x)(n/i)(m/i)}\)

有一个\((n/i)(m/i)\)，这个明显可以数论分块，但那个\(\mu(i/x)\)就不太好搞了，把他压进去

\(ans=\Pi_{i=1}^n(\Pi_{x|i}fib[x]^{\mu(i/x)})^{(n/i)(m/i)}\)

就可以预处理\(f[i]=(\Pi_{x|i}fib[x]^{\mu(i/x)})\)了

#include<bits/stdc++.h>

#define il inline

#define vd void

#define mod 1000000007

#define Mod 1000000006

typedef long long ll;

il int gi(){

    int x=0,f=1;

    char ch=getchar();

    while(!isdigit(ch)){

        if(ch=='-')f=-1;

        ch=getchar();

    }

    while(isdigit(ch))x=x*10+ch-'0',ch=getchar();

    return x*f;

}

int pri[1000010],pr,mu[1000010],yes[1000010];

int fib[1000010],ifib[1000010];

int f[1000010],g[1000010];

il int Pow(int x,int y){

    int ret=1;

    while(y){

        if(y&1)ret=1ll*ret*x%mod;

        x=1ll*x*x%mod;y>>=1;

    }

    return ret;

}

int main(){

    mu[1]=1;

    for(int i=2;i<=1000000;++i){

        if(!yes[i])mu[i]=-1,pri[++pr]=i;

        for(int j=1;i*pri[j]<=1000000&&j<=pr;++j){

            yes[i*pri[j]]=1;

            if(i%pri[j]==0){mu[i*pri[j]]=0;break;}

            mu[i*pri[j]]=-mu[i];

        }

    }

    fib[1]=1;for(int i=2;i<=1000000;++i)fib[i]=(fib[i-1]+fib[i-2])%mod;

    for(int i=1;i<=1000000;++i)ifib[i]=Pow(fib[i],mod-2);

    for(int i=1;i<=1000000;++i)f[i]=1;

    for(int i=1;i<=1000000;++i)

        for(int j=i;j<=1000000;j+=i)

            if(mu[j/i]==1)f[j]=1ll*f[j]*fib[i]%mod;

            else if(mu[j/i]==-1)f[j]=1ll*f[j]*ifib[i]%mod;

    for(int i=2;i<=1000000;++i)f[i]=1ll*f[i-1]*f[i]%mod;

    g[0]=1;for(int i=1;i<=1000000;++i)g[i]=Pow(f[i],mod-2);

    int T=gi(),n,m,ans;

    while(T--){

        n=gi(),m=gi();

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

        ans=1;

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

            int j=std::min(n/(n/i),m/(m/i));

            ans=1ll*ans*Pow(1ll*f[j]*g[i-1]%mod,(int)(1ll*(n/i)*(m/i)%Mod))%mod;

            i=j;

        }

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

    }

    return 0;

}