题目描述

Description

Doris刚刚学习了fibonacci数列。用f[i]表示数列的第i项，那么
f[0]=0
f[1]=1
f[n]=f[n-1]+f[n-2],n>=2
Doris用老师的超级计算机生成了一个n×m的表格，第i行第j列的格子中的数是f[gcd(i,j)]，其中gcd(i,j)表示i,
j的最大公约数。Doris的表格中共有n×m个数，她想知道这些数的乘积是多少。答案对10^9+7取模。

Input

有多组测试数据。
第一个一个数T，表示数据组数。
接下来T行，每行两个数n,m
T<=1000,1<=n,m<=10^6

Output

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

Sample Input

3
2 3
4 5
6 7

Sample Output

1
6
960

题目分析

求 其中是斐波那契数列





然后求解即可
注意当时 计算逆元

#include <cstdio>
#include <cstring>
#include <set>
#include <map>
#include <vector>
#include <cmath>
#include <queue>
#include <algorithm>
using namespace std;
int n,m,t;
int mu[1000010],prime[1000010];
long long f[1000010],g[1000010],mod=1000000007;
long long f2[1000010],g2[1000010];
long long ksm(long long x,long long y)
{
    long long sum=1;
    while(y)
    {
        if(y&1) sum=(sum*x)%mod;
        x=(x*x)%mod,y>>=1;
    }
    return sum;
}
bool vis[1000010];
void init()
{
    mu[1]=1;
    f[0]=0,f[1]=f2[1]=1;
    for(int i=2;i<=1000000;i++)
    {
        f[i]=(f[i-1]+f[i-2])%mod;
        f2[i]=ksm(f[i],mod-2);
        if(!vis[i]) prime[++prime[0]]=i,mu[i]=-1;
        for(int j=1;j<=prime[0]&&i*prime[j]<=1000000;j++)
        {
            vis[i*prime[j]]=1;
            if(i%prime[j]) mu[i*prime[j]]=-mu[i];
            else break;
        }
    }
    for(int i=1;i<=1000000;i++) g[i]=1;
    for(int i=1;i<=1000000;i++)
        for(int j=i;j<=1000000;j+=i)
        {
            if(mu[j/i]==1) g[j]=(g[j]*f[i])%mod;
            if(mu[j/i]==-1) g[j]=(g[j]*f2[i])%mod;
        }
    g[0]=g2[0]=1;
    for(int i=1;i<=1000000;i++)
        g[i]=g[i-1]*g[i]%mod,g2[i]=ksm(g[i],mod-2);
}   
void work(int x,int y)
{
    long long ans=1;
    int last=0;
    if(x>y) swap(x,y);
    for(int i=1;i<=x;i=last+1)
    {
        last=min(x/(x/i),y/(y/i));
        ans=(ans*ksm(g[last]*g2[i-1]%mod,(long long)(x/i)*(y/i)))%mod;
    }
    printf("%lld\n",ans%mod);
}
int main()
{   
    scanf("%d",&t);
    init();
    while(t--)
        scanf("%d%d",&n,&m),work(n,m);
    return 0;
}