【Luogu】P3704数字表格（莫比乌斯反演+大胆暴力）

　　题目链接

　　给你们讲个笑话：Konoset是个sb，他快速幂的时候把幂次取模了。

　　原式差不多就是这样吧$\prod\limits_{i=1}^{n}\prod\limits_{j=1}^{m}f[gcd(i,j)]$

　　然后我们枚举gcd(i,j)

　　可以变换一下

　　$\prod\limits_{w=1}^{min(n,m)}f[w]^{\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{m}[gcd(i,j)==w]}$

　　然后上面那个玩意搞搞可以反演一下

　　变为$\prod\limits_{w=1}^{min(n,m)}f[w]^{\sum\limits_{w|d}\mu(\frac{d}{w})\frac{n}{d}\frac{m}{d}}$

　　上面那个玩意显然=$\sum\limits_{d}\mu(d)\frac{n}{dw}\frac{m}{dw}$

　　然后枚举T=dw

　　指数变为$\sum\limits_{\frac{T}{w}}\mu(\frac{T}{w})\frac{n}{T}\frac{m}{T}$

　　然后把上面那个cigma搬到下面来

　　变成累乘

　　然后改成枚举T，中间预处理前缀积后面n除以Tm除以T的部分数论分块

　　这题是真的恶心

#include<cstdio>

#include<cstdlib>

#include<cstring>

#include<algorithm>

#include<cctype>

#define maxn 1000020

#define mod 1000000007

using namespace std;

inline long long read(){

    long long num=,f=;

    char ch=getchar();

    while(!isdigit(ch)){

        if(ch=='-')    f=-;

        ch=getchar();

    }

    while(isdigit(ch)){

        num=num*+ch-'';

        ch=getchar();

    }

    return num*f;

}

long long fib[maxn];

long long sum[maxn];

long long mul[maxn];

long long ni[maxn];

int miu[maxn];

bool vis[maxn];

int prime[maxn],num;

long long pow(long long n,long long x){

    long long ans=;

    while(x){

        if(x&)    ans=(ans*n)%mod;

        n=(n*n)%mod;

        x>>=;

    }

    return ans;

}

int main(){

    fib[]=;fib[]=vis[]=vis[]=miu[]=;

    for(int i=;i<maxn;++i){

        if(vis[i]==){

            prime[++num]=i;

            miu[i]=-;

        }

        for(int j=;j<=num&&i*prime[j]<maxn;++j){

            vis[i*prime[j]]=;

            if(i%prime[j]==)    break;

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

        }

    }

    for(int i=;i<maxn;++i){

        fib[i]=(fib[i-]+fib[i-])%mod;

        sum[i]=;

    }

    sum[]=;

    for(int i=;i<maxn;++i){

        long long now=fib[i],ret=pow(now,mod-);

        for(register int j=i;j<maxn;j+=i){

            if(miu[j/i]==)    sum[j]=(sum[j]*now)%mod;

            else            sum[j]=(sum[j]*ret)%mod;

        }

    }

    mul[]=sum[];mul[]=;ni[]=ni[]=;

    for(int i=;i<maxn;++i){

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

        ni[i]=pow(mul[i],mod-);

    }

    int T=read();

    while(T--){

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

        int l=;long long ans=;int top=min(n,m);

        while(l<=top){

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

            ans*=pow(mul[r]*ni[l-]%mod,(n/l)*(m/l));

            ans%=mod;

            l=r+;

        }

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

    }

    return ;

}

巴特西

【Luogu】P3704数字表格（莫比乌斯反演+大胆暴力）

最新文章

热门文章