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
2 3
4 5
6 7
Sample Output
1
6
960
6
960
HINT
Source
鸣谢infinityedge上传
Solution
莫比乌斯反演。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 |
#include<iostream> #include<cstdio> #include<algorithm> #include<cmath> #include<cstring> #define ll long long #define mo 1000000007 using namespace std; int T,mu[1000100],prime[1000100],tot; ll f[1000100],g[1000100],inv[1000100],Inv[1000100]; struct node{int x,y;}Q[1005]; bool flag[1000100]; ll mi(ll x,ll y) { y%=(mo-1); ll ans=1; while (y) { if (y&1) ans=ans*x%mo; x=x*x%mo; y>>=1; } return ans; } void Init(int n) { mu[1]=1; f[0]=0;f[1]=1; inv[0]=0;inv[1]=1; for (int i=2;i<=n;i++) f[i]=(f[i-1]+f[i-2])%mo,inv[i]=mi(f[i],mo-2)%mo; for (int i=2;i<=n;i++) { if (!flag[i]) { prime[++tot]=i;mu[i]=-1;} for (int j=1;j<=tot;j++) { if (prime[j]*i>n) break; flag[prime[j]*i]=1; if (i%prime[j]==0) { mu[i*prime[j]]=0;break;} else mu[i*prime[j]]=-mu[i]; } } for (int i=1;i<=n;i++) g[i]=1; for (int i=1;i<=n;i++) for (int j=1;j<=n/i;j++) { if (!mu[j]) continue; if (mu[j]>0) g[i*j]=g[i*j]*f[i]%mo; else g[i*j]=g[i*j]*inv[i]%mo; } g[0]=1;Inv[0]=1; for (int i=1;i<=n;i++) g[i]=g[i-1]*g[i]%mo,Inv[i]=mi(g[i],mo-2)%mo; } void solve(int x,int y) { ll ans=1; int j; for (int i=1;i<=x&&i<=y;i=j+1) { j=min(x/(x/i),y/(y/i)); ans=ans*mi((g[j]*Inv[i-1]%mo),(ll)(x/i)*(y/i))%mo; } printf("%lld\n",ans); } int main() { scanf("%d",&T); int Max=0; for (int i=1;i<=T;i++) { scanf("%d%d",&Q[i].x,&Q[i].y);Max=max(Max,max(Q[i].x,Q[i].y));} Init(Max); for (int i=1;i<=T;i++) solve(Q[i].x,Q[i].y); return 0; } |
