C++14(g++5.4) 解法, 执行用时: 185ms, 内存消耗: 8596K, 提交时间: 2019-02-15 21:23:39

#include<stdio.h>
#include<algorithm>
#include<math.h>
#define fo(i,a,b) for(int i=a;i<=b;i++)
#define fd(i,a,b) for(int i=a;i>=b;i--)
int T,n,m,pri[260000],g[260000],pt,mu[260000],j,i,te;
bool isp[260000];
long long f[260000],ans,G[260000],inv[100],pre[260000],ing[260000];
const int p=1e9+7;
inline long long qpow(long long a,long long n){
	if (a==1) return 1;//!!!
	long long s=1;
	while (n){
		if (n&1) s=s*a%p;
		a=a*a%p;
		n>>=1;
	}
	return s;
}
int main(){
	inv[1]=1;
	fo(i,2,100) inv[i]=qpow(i,p-2);
	g[1]=1;G[1]=1;mu[1]=1;
	fo(i,2,250000){
		G[i]=1;
		if (!isp[i]){
			pri[++pt]=i;
			g[i]=1;
			mu[i]=-1;
		}
		fo(j,1,pt){
			te=i*pri[j];
			if (te>250000) break;
			isp[te]=1;
			g[te]=g[i]+1;
			if (i%pri[j]==0) break;//!!!!!
			mu[te]=-mu[i];//!!!!!!!!
		}
	}
	fo(i,1,250000){
		if (mu[i]==1) for(int j=i,k=1;j<=250000;j+=i,k++) G[j]=G[j]*g[k]%p;
		if (mu[i]==-1) for(int j=i,k=1;j<=250000;j+=i,k++) G[j]=G[j]*inv[g[k]]%p; 
	}
	pre[0]=ing[0]=1;
	fo(i,1,250000) pre[i]=pre[i-1]*G[i]%p;
	ing[250000]=qpow(pre[250000],p-2);
	fd(i,249999,1) ing[i]=ing[i+1]*G[i+1]%p;
//	fo(i,1,10) printf("%lld\n",ing[i]*pre[i]%p);
//	printf("%d\n",g[40]);//4
	scanf("%d",&T);
	while (T--){
		scanf("%d%d",&n,&m);
		if (n>m) std::swap(n,m);
//		ans=1;
//		fd(i,n,4){
//			f[i]=(n/i)*1ll*(m/i);
//			for(int j=i+i;j<=n;j+=i) f[i]-=f[j];
//			ans=ans*qpow(g[i],f[i])%p;
//		}
//		printf("%lld\n",ans);
//		ans=1;
//		fo(i,1,n) ans=ans*qpow(G[i],(n/i)*1ll*(m/i))%p;
//		printf("%lld\n",ans);
		ans=1;
		i=1;
		while (i<=n){
			j=std::min(n/(n/i),m/(m/i));
			ans=ans*qpow(pre[j]*ing[i-1]%p,(n/i)*1ll*(m/i))%p;//pre[i]*ing[j-1]!!!!
			i=j+1;
		}
		printf("%lld\n",ans);
	}
	return 0;
}

C++11(clang++ 3.9) 解法, 执行用时: 483ms, 内存消耗: 4832K, 提交时间: 2020-03-25 15:22:08

#include<iostream>
#include<cstdio>
const int N=250005;
typedef long long ll;
const ll mod=1e9+7;
ll qpow(ll x,ll y)
{
	ll res=1;
	for(;y;y>>=1,x=x*x%mod)
	if(y&1) res=res*x%mod;
	return res;
}
int u[N],prime[N],cnt,g[N];
bool vis[N];
ll f[N];
void init()
{
	g[1]=1;
	f[1]=1;
	u[1]=1;
	for(int i=2;i<N;i++)
	{
		if(!vis[i])
		u[i]=-1,prime[cnt++]=i,g[i]=1;
		for(int j=0;j<cnt&&i*prime[j]<N;j++)
		{
			vis[i*prime[j]]=1;
			g[i*prime[j]]=g[i]+1;
			if(i%prime[j]==0) break;
			u[i*prime[j]]=-u[i];
		}
		f[i]=1;
	}
	for(int i=1;i<N;i++)
	for(int j=i;j<N;j+=i)
	{
		if(!u[j/i]) continue;
		f[j]=f[j]*(u[j/i]>0?g[i]:qpow(g[i],mod-2))%mod;
	}
	for(int i=2;i<N;i++)
	f[i]=f[i]*f[i-1]%mod;
	f[0]=1;
}
int main()
{
	int T,n,m;
	init();
	scanf("%d",&T);
	while(T--)
	{
		scanf("%d%d",&n,&m);
		if(n>m) std::swap(n,m);
		ll ans=1;
		for(int i=1,j;i<=n;i=j+1)
		{
			j=std::min(n/(n/i),m/(m/i));
			ans=ans*qpow(f[j]*qpow(f[i-1],mod-2)%mod,1LL*(n/i)*(m/i))%mod;
		}
		printf("%lld\n",ans);
	}
	return 0;
}