P3704 [SDOI2017]数字表格（莫比乌斯反演）

[题目链接] https://www.luogu.org/problemnew/show/P3704

[题解] https://www.luogu.org/blog/cjyyb/solution-p3704

题目描述

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)]\)

Doris的表格中共有\(n×m\)个数，她想知道这些数的乘积是多少。

答案对\(10^9+7\)取模。

/*

-----------------------

https://www.luogu.org/blog/cjyyb/solution-p3704

-----------------------

常规套路化式子,一定要看清题...

枚举两个数d和x转化后还是枚举两个数T(=dx)和d

预处理的初始化,一定要注意

最后预处理O(NlogN),每个询问O(√N),O(√N)级别的询问

-----------------------2019.2.15

*/

#include<bits/stdc++.h>

using namespace std;

#define int long long

typedef long long LL;

const int INF=1e9+7;

inline LL read(){

    register LL x=0,f=1;register char c=getchar();

    while(c<48||c>57){if(c=='-')f=-1;c=getchar();}

    while(c>=48&&c<=57)x=(x<<3)+(x<<1)+(c&15),c=getchar();

    return f*x;

}

const int MAXN=1e6+5;

const int mod=1e9+7;

LL mul[MAXN],f[MAXN],invf[MAXN];

LL ans,tmp;

int mu[MAXN],prime[MAXN];

bool vis[MAXN];

int T,n,m;

inline int qpow(int a,int b){// a要开long long !!!

    LL res=1;

    while(b){

        if(b&1) (res*=a)%=mod;

        (a*=a)%=mod;

        b>>=1;

    }

    return res;

}

inline void init(int n){

    mu[1]=1;

    f[1]=invf[1]=1;///

    mul[0]=mul[1]=1;///

    for(int i=2;i<=n;i++){

        f[i]=(f[i-1]+f[i-2])%mod;

        invf[i]=qpow(f[i],mod-2);

        mul[i]=1;///

        if(!vis[i]) prime[++prime[0]]=i,mu[i]=-1;

        for(int j=1;j<=prime[0]&&i*prime[j]<=n;j++){

            vis[i*prime[j]]=true;

            if(i%prime[j]==0) break;///经常错这里

            mu[i*prime[j]]=-mu[i];

        }

    }

    for(int i=1;i<=n;i++){

        if(mu[i]==0) continue;

        for(int j=i;j<=n;j+=i)

            (mul[j]*=(mu[i]==1)?f[j/i]:invf[j/i])%=mod;//"暴力"计算

    }

    for(int i=2;i<=n;i++)

        (mul[i]*=mul[i-1])%=mod;

}

signed main(){

    T=read();

    init(1e6);

    while(T--){

        n=read(),m=read();

        if(n>m) swap(n,m);

        ans=1;

        for(int l=1,r;l<=n;l=r+1){

            r=min(n/(n/l),m/(m/l));

            tmp=mul[r]*qpow(mul[l-1],mod-2)%mod;

            (ans*=qpow(tmp,(n/l)*(m/l)%(mod-1)))%=mod;

        }

        printf("%lld\n",ans);

    }

}

巴特西

P3704 [SDOI2017]数字表格（莫比乌斯反演）

题目描述

最新文章

热门文章

巴特西

P3704 [SDOI2017]数字表格 （莫比乌斯反演）

题目描述

最新文章

热门文章

P3704 [SDOI2017]数字表格（莫比乌斯反演）