一、題目描述：

　　用 $f_i$ 表示斐波那契數列的第 $i$ 項，那么有：

　　$ f_0=0,f_1=1;f_n=f_{n-1}+f_{n-2},n\ge2 $

　　現在有一個 $n$ 行 $m$ 列的數字表格，第 $i$ 行第 $j$ 列的數字是 $f_{\gcd(i,j)}$ 。

　　求這個表格所有數的乘積。共有 $T$ 組數據，答案對 $10^9+7$ 取模。

　　數據范圍：$1\le T\le 10^3,1\le n,m\le 10^6$ 。

 二、解題思路：

　　我迄今為止做過的最難的莫比烏斯反演題！

　　話不多說，直接開始推式子。

　　$$\prod_{i=1}^{n}\prod_{j=1}^mf(\gcd(i,j))=$$

　　$$\prod_{d=1}^n\prod_{i=1}^{n}\prod_{j=1}^m[\gcd(i,j)=d]f(d)=$$

　　$$\prod_{d=1}^nf(d)^{\sum_{i=1}^{n}\sum_{j=1}^m[\gcd(i,j)=d]}=$$

　　$$\prod_{d=1}^nf(d)^{\sum_{i=1}^{n/d}\sum_{j=1}^{m/d}[\gcd(i,j)=1]}$$

　　$$令g(x,y)=\sum_{i=1}^x\sum_{j=1}^y[\gcd(i,j)=1]$$

　　$$則原式=\prod_{d=1}^nf(d)^{g(\lfloor\frac{n}w0obha2h00 \rfloor,\lfloor\frac{m}w0obha2h00 \rfloor)}$$

　　$$考慮g(x,y)=\sum_{i=1}^x\sum_{j=1}^y[\gcd(i,j)=1]=$$

　　$$\sum_{i=1}^x\sum_{j=1}^y\sum_{d\mid \gcd(x,y)}\mu(d)=\sum_{d=1}^x\mu(d)\times \lfloor\frac{x}w0obha2h00 \rfloor\lfloor\frac{y}w0obha2h00 \rfloor$$

　　$$求出斐波那契數列的乘積前綴和，再求出逆元即可$$

　　$$時間復雜度O(T\times (n+\sqrt n\times log_2^n))$$

　　$$時間復雜度顯然過不去，考慮優化$$

　　$$將g(x,y)帶入原式，得到原式=\prod_{d=1}^nf(d)^{\sum_{k=1}^{n/d}\mu(k)\times \lfloor\frac{n}{dk} \rfloor\lfloor\frac{m}{dk} \rfloor}$$

　　$$令T=dk,則原式=\prod_{T=1}^n \left(\prod_{d\mid T}f(d)^{\mu(\frac{T}w0obha2h00)}\right)^{ \lfloor\frac{n}{T} \rfloor\lfloor\frac{m}{T} \rfloor}$$

　　$$令g(x)=\prod_{d\mid x}f(d)^{\mu(\frac{x}w0obha2h00)},原式=\prod_{T=1}^n g(T)^{ \lfloor\frac{n}{T} \rfloor\lfloor\frac{m}{T} \rfloor}$$

　　$$考，原來里面的g(x)可以直接暴力求出來，調和級數!$$

　　$$時間復雜度O((T\sqrt n+n)\times log_2^n)$$

 三、完整代碼：

 1 #include<iostream>
 2 #define N 1000010
 3 #define lim 1000000
 4 #define ll long long
 5 #define M 1000000007
 6 using namespace std;
 7 ll ans,f[N],g[N],inf[N],ing[N];
 8 int T,n,m,cnt,mu[N],p[N],vis[N];
 9 ll ksm(ll base,ll q)
10 {
11     ll res=1;
12     while(q){
13         if(q&1) res*=base,res%=M;
14         base*=base,base%=M,q>>=1;
15     }
16     return res;
17 }
18 void pre_work()
19 {
20     mu[1]=f[1]=g[0]=ing[0]=1;
21     for(int i=2;i<=lim;i++)
22         f[i]=(f[i-1]+f[i-2])%M;
23     for(int i=1;i<=lim;i++)
24         inf[i]=ksm(f[i],M-2),g[i]=1;
25     for(int i=2;i<=lim;i++)
26     {
27         if(!vis[i]) p[++cnt]=i,mu[i]=-1;
28         for(int j=1;j<=cnt&&i*p[j]<=lim;j++)
29         {
30             vis[i*p[j]]=1;
31             if(i%p[j]==0)break;
32             mu[i*p[j]]=-mu[i];
33         }
34     }
35     for(int i=1;i<=lim;i++)
36         for(ll j=i;j<=lim;j+=i)
37         {
38             if(mu[j/i]==1) g[j]=g[j]*f[i]%M;
39             if(mu[j/i]==-1) g[j]=g[j]*inf[i]%M;
40         }
41     for(int i=1;i<=lim;i++)
42         g[i]=g[i]*g[i-1]%M,ing[i]=ksm(g[i],M-2);
43 }
44 void solve()
45 {
46     cin>>n>>m; ans=1;
47     if(n>m) swap(n,m);
48     for(int l=1,r;l<=n;l=r+1)
49     {
50         r=min(n/(n/l),m/(m/l));ans%=M;
51         ans*=ksm(ing[l-1]*g[r]%M,1ll*(n/l)*(m/l)%(M-1));
52     }
53     cout<<ans%M<<'\n';
54 }
55 int main()
56 {
57     ios::sync_with_stdio(false);
58     cin.tie(0);cout.tie(0);
59     cin>>T;pre_work();
60     for(int i=1;i<=T;i++)
61         solve();
62     return 0;
63 }

四、寫題心得：

　　收獲很大，了解了一些套路和技巧。收獲經驗如下：

　　$1、當式子化不出來/時間復雜度過高的時候，可以考慮將函數帶入原式中，換元，看看有沒有什么新發現。=> Exp++!$

　　$2、時刻記得很多東西都可以預處理。如果函數可以寫成類卷積的形式，往往可以調和級數\ O(nIn^n)\ 地預處理=> Exp++!$

　　$3、當快速冪的冪次需要取模的時候，是對\ mod-1\ 取模\ !\ 根據費馬小定理，a^{p-1}\equiv 1\ (\bmod p)\ 。這里要特別注意！=> Exp++!$