C++(g++ 7.5.0) 解法, 执行用时: 836ms, 内存消耗: 33436K, 提交时间: 2022-11-18 14:42:30

#include <bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
const int M = 1e6 + 10, N = 1e6, mod = 1e9 + 7;

int primes[M], mu[M], cnt;
bool st[M];
int s[M], f[M], F[M];
int infac[M];

int qmi(int a, int b)
{
	int res = 1;
	while(b)
	{
		if(b & 1)res = res * a % mod;
		a = a * a % mod;
		b >>= 1;
	}
	return res;
}

void get_mu()
{
	F[0] = mu[0] = F[1] = f[1] = infac[1] = 1;
	infac[0] = mu[1] = 1;
	for(int i = 2; i <= N; i++)
	{
		F[i] = 1;
		f[i] = (f[i - 1] + f[i - 2]) % mod;
		infac[i] = qmi(f[i], mod - 2);
		if(!st[i])primes[++cnt] = i, mu[i] = -1;
		for(int j = 1; j <= cnt && primes[j] <= N / i; j++)
		{
			int x = primes[j] * i;
			st[x] = 1;
			if(i % primes[j] == 0)break;
			mu[x] = -mu[i];
		}
	}

	//i枚举的是约数  j是倍数
	for(int i = 1; i <= N; i++)
	{
		if(!mu[i])continue;
		for(int j = i; j <= N; j += i)
		{
			if(mu[i] == -1)F[j] = F[j] * infac[j / i] % mod;
			else F[j] = F[j] * f[j / i] % mod;
		}
	}
	
	for(int i = 2; i <= N; i++)
	{
		F[i] = F[i] * F[i - 1] % mod;
	}
}

void solve()
{
	int n, m;
	cin >> n >> m;
	if(n > m)swap(n, m);
	int ans = 1;
	for(int i = 1, j; i <= n; i = j + 1)
	{
		j = min(n / (n / i), m / (m / i));
		ans = (ans * qmi((F[j] * qmi(F[i - 1], mod - 2) % mod) % mod, (n / i) * (m / i))) % mod;
	}
	cout << ans << endl;
}

signed main()
{
	ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
	int T = 1;
	get_mu();
	cin >> T;
	while(T--)solve();
	return 0;
}

C++14(g++5.4) 解法, 执行用时: 884ms, 内存消耗: 31844K, 提交时间: 2019-08-29 17:56:20

#include<bits/stdc++.h>
#include<tr1/unordered_map>
typedef long long ll;
using namespace std;
const int maxn=1e6+10;
const int mod=1e9+7;
int prime[maxn],mu[maxn],T,n,m;
ll f[maxn],g[maxn],_f[maxn];
ll ksm(ll a,ll n)
{
    ll res=1;
    while(n)
    {
        if(n&1) res=res*a%mod;
        a=a*a%mod;
        n>>=1;
    }
    return res;
}
void get_prime()
{
	prime[0]=0;
    mu[1]=f[1]=_f[1]=g[0]=1;g[1]=1;
    for(int i=2;i<maxn;i++)
    {
        if(!prime[i])   {prime[++prime[0]]=i;mu[i]=-1;}
        for(int j=1;j<=prime[0]&&prime[j]*i<maxn;j++)
        {
            prime[i*prime[j]]=1;
            if(i%prime[j]==0)   break;
            mu[i*prime[j]]=-mu[i];
        }
        f[i]=(f[i-1]+f[i-2])%mod;
        _f[i]=ksm(f[i],mod-2);
        g[i]=1;
    }
    for(int i=1;i<maxn;i++)
    {
        g[i]=g[i-1]*g[i]%mod;
        if(!mu[i])  continue;
        for(int j=1;i*j<maxn;j++)
            g[i*j]=g[i*j]*(mu[i]==-1?_f[j]:f[j])%mod;
    }
}
 
int main()
{
    get_prime();
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d%d",&n,&m);
        if(n>m)  swap(n,m);
        ll ans=1;
        for(int l=1,r;l<=n;l=r+1)
        {
            r=min(n/(n/l),m/(m/l));
            ans=1ll*ans*ksm(g[r]*ksm(g[l-1],mod-2)%mod,1ll*(n/l)*(m/l)%(mod-1))%mod;
        }
        printf("%lld\n",(ans+mod)%mod);
    }
    return 0;
}

C++11(clang++ 3.9) 解法, 执行用时: 768ms, 内存消耗: 16228K, 提交时间: 2019-10-12 08:27:56

#include<cstdio>
#include<algorithm>
using namespace std;
const long long mod=1e9+7;
const int N=1e6;
long long f[1000005],nf[1000005];
long long Qpow(long long x,long long y)
{
	x%=mod;
	long long ans=1;
	while(y)
	{
		if(y&1)ans=ans*x%mod;
		x=x*x%mod;
		y>>=1;
	}
	return ans;
}
int main()
{
	f[0]=0;
	f[1]=1;
	for(int i=2;i<=N;i++)
		f[i]=(f[i-1]+f[i-2])%mod;
	for(int i=1;i<=N;i++)
	{
		nf[i]=Qpow(f[i],mod-2);
		for(int j=2*i;j<=N;j+=i)
			f[j]=f[j]*nf[i]%mod;
	}
	for(int i=1;i<=N;i++)
		nf[i]=Qpow(f[i],mod-2);
	for(int i=2;i<=N;i++)
		f[i]=f[i]*f[i-1]%mod,nf[i]=nf[i]*nf[i-1]%mod;
	f[0]=nf[0]=1;
	int T;
	int n,m;
	scanf("%d",&T);
	while(T--)
	{
		long long ans=1;
		scanf("%d%d",&n,&m);
		for(int i=1;i<=n&&i<=m;i++)
		{
			int j=min(n/(n/i),m/(m/i));
			//printf("%lld<-%lld\n",f[j]*nf[i-1]%mod,1LL*(n/i)*(m/i));
			ans=ans*Qpow(f[j]*nf[i-1]%mod,1LL*(n/i)*(m/i))%mod;
			i=j;
		}
		printf("%lld\n",ans);
	}
}