題目描述

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：?
3 2 3 4 5 6 7 輸出樣例#1：?
1 6 960

說明

對$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<bits/stdc++.h> #define ll long long #define maxn 1000005 using 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; }

　　

轉載于:https://www.cnblogs.com/JYYHH/p/8506168.html

總結

以上是生活随笔為你收集整理的[SDOI2017]数字表格的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。