题目描述

Doris刚刚学习了fibonacci数列。用$f[i]$ 表示数列的第$i$ 项，那么

$f[0]=0$ ,$f[1]=1$ ,

$f[n]=f[n-1]+f[n-2],n\geq 2$

Doris用老师的超级计算机生成了一个$n×m$ 的表格，

第$i$ 行第$j$ 列的格子中的数是$f[\gcd(i,j)]$ ，其中$\gcd(i,j)$ 表示$i,j$ 的最大公约数。

Doris的表格中共有$n×m$ 个数，她想知道这些数的乘积是多少。

答案对$10^9+7$ 取模。

输入输出格式

输入格式：

 

有多组测试数据。

第一个一个数$T$ ，表示数据组数。

接下来$T$ 行，每行两个数$n,m$

 

输出格式：

 

输出$T$ 行，第$i$ 行的数是第$i$ 组数据的结果

 

输入输出样例

输入样例#1：

 

32 34 56 7

输出样例#1：

 

16960

说明

对$10\%$ 的数据，$1\leq n,m\leq 100$

对$30\%$ 的数据，$1\leq n,m\leq 1000$

另外存在$30\%$ 的数据，$T\leq 3$

对$100\%$ 的数据，$T\leq1000,1\leq n,m\leq 10^6$

时间限制：5s

内存限制：128MB

 

 

以前做过了，直接上代码。

#include
     
      #define ll long long#define maxn 1000005using namespace std;const int ha=1000000007;const int mo=1000000006;bool v[maxn];int zs[maxn/5],t=0,miu[maxn];int f[maxn],n,m,T,g[maxn],ni[maxn];inline int add(int x,int y){	x+=y;	return x>=ha?x-ha:x;}inline int ksm(int x,int y){	int an=1;	for(;y;y>>=1,x=x*(ll)x%ha) if(y&1) an=an*(ll)x%ha;	return an;}inline void init(){	miu[1]=1;	for(int i=2;i<=1000000;i++){		if(!v[i]) zs[++t]=i,miu[i]=-1;		for(int j=1,u;j<=t&&(u=zs[j]*i)<=1000000;j++){			v[u]=1;			if(!(i%zs[j])) break;			miu[u]=-miu[i];		}	}		f[1]=f[2]=ni[1]=ni[2]=1;	for(int i=3;i<=1000000;i++) f[i]=add(f[i-1],f[i-2]),ni[i]=ksm(f[i],ha-2);	fill(g,g+1000001,1);	for(int i=1;i<=1000000;i++)		for(int j=i;j<=1000000;j+=i)		    if(miu[j/i]==1) g[j]=g[j]*(ll)f[i]%ha;		    else if(miu[j/i]) g[j]=g[j]*(ll)ni[i]%ha;		for(int i=1;i<=1000000;i++) g[i]=g[i]*(ll)g[i-1]%ha;}inline int query(int x,int y){	int an=1,nowx,nowy;	for(int i=1,j;i<=x;i=j+1){		nowx=x/i,nowy=y/i;		j=min(x/nowx,y/nowy);		an=an*(ll)ksm(g[j]*(ll)ksm(g[i-1],ha-2)%ha,nowx*(ll)nowy%mo)%ha;	}		return an;}int main(){	init();	scanf("%d",&T);	while(T--){		scanf("%d%d",&n,&m);		if(n>m) swap(n,m);		printf("%d\n",query(n,m));	}		return 0;}