传送门

题意：

定义 f[0]=0,f[1]=1,f[n]=f[n−1]+f[n−2],n≥2 f [ 0 ] = 0 , f [ 1 ] = 1 , f [ n ] = f [ n − 1 ] + f [ n − 2 ] , n ≥ 2

给出n,m，求 Πni=1Πmj=1f[gcd(i,j)]%1e9+7 Π i = 1 n Π j = 1 m f [ g c d ( i , j ) ] % 1 e 9 + 7

多组数据，n,m<=1e6

Solution：

做多了就会发现莫比乌斯反演都是套路题

然而就算知道是套路题自己也推不出来QAQ

首先改变式子为枚举gcd

原式

=∏min(n,m)d=1f[d]∑ni=1∑mj=1[gcd(i,j)==d] = ∏ d = 1 m i n ( n , m ) f [ d ] ∑ i = 1 n ∑ j = 1 m [ g c d ( i , j ) == d ]

=∏min(n,m)d=1f[d]∑⌊nd⌋i=1∑⌊md⌋j=1[gcd(i,j)==1] = ∏ d = 1 m i n ( n , m ) f [ d ] ∑ i = 1 ⌊ n d ⌋ ∑ j = 1 ⌊ m d ⌋ [ g c d ( i , j ) == 1 ]

=∏min(n,m)d=1f[d]∑⌊min(n,m)d⌋k=1μ(k)⌊nkd⌋⌊mkd⌋ = ∏ d = 1 m i n ( n , m ) f [ d ] ∑ k = 1 ⌊ m i n ( n , m ) d ⌋ μ ( k ) ⌊ n k d ⌋ ⌊ m k d ⌋

=∏min(n,m)d=1∏⌊min(n,m)d⌋k=1f[d]μ(k)⌊nkd⌋⌊mkd⌋ = ∏ d = 1 m i n ( n , m ) ∏ k = 1 ⌊ m i n ( n , m ) d ⌋ f [ d ] μ ( k ) ⌊ n k d ⌋ ⌊ m k d ⌋

上面的形态也是一个套路：转为枚举kd以及其约数，设p=kd

=∏min(n,m)p=1∏d|pf[d]μ(pd)⌊np⌋⌊mp⌋ = ∏ p = 1 m i n ( n , m ) ∏ d | p f [ d ] μ ( p d ) ⌊ n p ⌋ ⌊ m p ⌋

=∏min(n,m)p=1(∏d|pf[d]μ(pd))⌊np⌋⌊mp⌋ = ∏ p = 1 m i n ( n , m ) ( ∏ d | p f [ d ] μ ( p d ) ) ⌊ n p ⌋ ⌊ m p ⌋

现在我们就使括号里的那一坨独立了，我们就可以预处理出对于每个p括号内的值，求一个前缀积再用数论分块即可

预处理括号内的值可以枚举约数，复杂度为 O(n+n2+n3+...)=O(nlogn) O ( n + n 2 + n 3 + . . . ) = O ( n log ⁡ n )

数论分块+快速幂 总复杂度 O(Tn−−√logmod) O ( T n log ⁡ m o d )

代码：

#include<cstdio>
#include<iostream>
#include<cmath>
using namespace std;
int T,n,m;
int prim[200010],miu[1000010],cnt;
bool vis[1000010];
int fib[1000010],qzj[1000010];
int f[1000010][3];
const int mod=1e9+7;
void get_prim(int n)
{
    miu[1]=1;fib[0]=0;fib[1]=1;
    for (int i=2;i<=n;i++)
    {
        fib[i]=fib[i-1]+fib[i-2];if (fib[i]>=mod) fib[i]-=mod;
        if (!vis[i]) prim[++cnt]=i,vis[i]=1,miu[i]=-1;
        for (int j=1;j<=cnt&&prim[j]*i<=n;j++)
        {
            vis[prim[j]*i]=1;
            miu[prim[j]*i]=-miu[i];
            if (i%prim[j]==0) {miu[prim[j]*i]=0;break;}
        }
    }
}
int fast_pow(int x,int a)
{
    int ans=1;
    for (;a;a>>=1,x=1ll*x*x%mod)
        if (a&1) ans=1ll*ans*x%mod;
    return ans;
}
void get_xjb(int n)
{
    qzj[0]=1;
    for (int i=1;i<=n;i++) qzj[i]=1,f[i][0]=fast_pow(fib[i],mod-2),f[i][1]=1,f[i][2]=fib[i];
    for (int i=1;i<=n;i++)
        for (int j=i;j<=n;j+=i)
            qzj[j]=1ll*qzj[j]*f[i][miu[j/i]+1]%mod;
    for (int i=2;i<=n;i++) qzj[i]=1ll*qzj[i]*qzj[i-1]%mod; 
}
int read()
{
    int x=0,t=1;char ch=getchar();
    while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();
    if(ch=='-')t=-1,ch=getchar();
    while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();
    return x*t;
}
int main()
{
    get_prim(1000000);get_xjb(1000000);
    T=read();
    while (T--)
    {
        n=read();m=read();
        int ans=1,last=0;
        for (int i=1;i<=min(n,m);i=last+1)
        {
            last=min(n/(n/i),m/(m/i));
            int nw=1ll*qzj[last]*fast_pow(qzj[i-1],mod-2)%mod;
            ans=1ll*ans*fast_pow(nw,1ll*(n/i)*(m/i)%(mod-1))%mod; 
        }
        printf("%d\n",ans);
    }
}