luoguP5518 [MtOI2019]幽灵乐团 / 莫比乌斯反演基础练习题

一道毒瘤题目，题目链接：luoguP5518。

题意

题目大意：求 $ \prod\limits_{i=1} ^A\prod\limits_{j=1} ^B\prod\limits_{k=1} ^C\left(\dfrac{\operatorname{lcm}(i,j)}{\gcd(i,k)}\right) ^{f(type)} $ 。

其中 $ type\in $ \(\{0,1,2\}\) ， $ f(0)=1,f(1)=ijk,f(2)=\gcd(i,j,k) $ 。

题解

让我们先来推一下式子。

\[\begin{aligned} &\prod_{i=1}^A\prod_{j=1}^B\prod_{k=1}^C\left(\dfrac{\operatorname{lcm}(i,j)}{\gcd(i,k)}\right)^{f(type)}\\ =&\prod_{i=1}^A\prod_{j=1}^B\prod_{k=1}^C\left(\dfrac{\dfrac{ij}{\gcd(i,j)}}{\gcd(i,k)}\right)^{f(type)}&\operatorname{lcm}(i,j)=\dfrac{ij}{\gcd(i,j)}\\ =&\prod_{i=1}^A\prod_{j=1}^B\prod_{k=1}^C\left(\dfrac{ij}{\gcd(i,j)\gcd(i,k)}\right)^{f(type)}\\ =&\prod_{i=1}^A\prod_{j=1}^B\prod_{k=1}^C\dfrac{i^{f(type)}j^{f(type)}}{\gcd(i,j)^{f(type)}\gcd(i,k)^{f(type)}}\\ =&\dfrac{\left(\prod\limits_{i=1}^A\prod\limits_{j=1}^B\prod\limits_{k=1}^Ci^{f(type)}\right)\times\left(\prod\limits_{i=1}^A\prod\limits_{j=1}^B\prod\limits_{k=1}^Cj^{f(type)}\right)}{\left(\prod\limits_{i=1}^A\prod\limits_{j=1}^B\prod\limits_{k=1}^C\gcd(i,j)^{f(type)}\right)\times\left(\prod\limits_{i=1}^A\prod\limits_{j=1}^B\prod\limits_{k=1}^C\gcd(i,k)^{f(type)}\right)} \end{aligned} \]

实际上只需要知道 $ \prod\limits_{i=1}^ A\prod\limits_{j=1}^ B\prod\limits_{k=1}^ Ci^{f(type)} $ 和 $ \prod\limits_{i=1}^ A\prod\limits_{j=1}^ B\prod\limits_{k=1}^ C\gcd(i,j)^{f(type)} $ 的求法就可以了。

所以我们一共要推 $ 6 $ 个式子。

type=0

\[\begin{aligned} &\prod\limits_{i=1}^A\prod\limits_{j=1}^B\prod\limits_{k=1}^Ci\\ =&\prod\limits_{i=1}^Ai^{BC}&直接看 i 被乘了多少次 \end{aligned} \]

\[\begin{aligned} &\prod\limits_{i=1}^A\prod\limits_{j=1}^B\prod\limits_{k=1}^C\gcd(i,j)\\ =&\prod\limits_{i=1}^A\prod\limits_{j=1}^B\gcd(i,j)^C\\ =&\prod\limits_{p\in prime,m\ge0}\prod\limits_{i=1}^A\prod\limits_{j=1}^Bp^{C[p^m|\gcd(i,j)]}&枚举质数找\gcd,注意有的\gcd有多个相同质数\\ =&\prod\limits_{p\in prime,m\ge0}p^{\left\lfloor\frac{A}{p^m}\right\rfloor\left\lfloor\frac{B}{p^m}\right\rfloor C} \end{aligned} \]

第一个式子直接预处理阶乘，然后算 $ BC $ 次方。

第二个式子可以通过预处理筛出 $ p^m $ ，然后快速幂。

如果想要更快可以筛出所有 $ p^m $ 的前缀积，然后数论分块。

type=1

\[\begin{aligned} &\prod\limits_{i=1}^A\prod\limits_{j=1}^B\prod\limits_{k=1}^Ci^{ijk}\\ =&\prod\limits_{i=1}^Ai^{i\sum\limits_{j=1}^B\kern{4pt}\sum\limits_{k=1}^C\kern{2pt}jk}\\ =&\prod\limits_{i=1}^Ai^{i(\sum\limits_{j=1}^Bj)(\sum\limits_{k=1}^Ck)}\\ =&\prod\limits_{i=1}^Ai^{if(B)f(C)}&f(n)=\dfrac{n(n+1)}{2} \end{aligned} \]

\[\begin{aligned} &\prod\limits_{i=1}^A\prod\limits_{j=1}^B\prod\limits_{k=1}^C\gcd(i,j)^{ijk}\\ =&\prod\limits_{i=1}^A\prod\limits_{j=1}^B\gcd(i,j)^{ij\sum\limits_{k=1}^Ck}\\ =&\prod\limits_{i=1}^A\prod\limits_{j=1}^B\gcd(i,j)^{ijf(C)}\\ =&\prod_{p\in prime,m\ge0}\prod\limits_{i=1}^A\prod\limits_{j=1}^Bp^{[p^m|\gcd(i,j)]ijf(C)}&和上面一样的方法\\ =&\prod_{p\in prime,m\ge0}p^{p^{2m}\kern{3pt}f\left(\left\lfloor\frac{A}{p^m}\right\rfloor\right)f\left(\left\lfloor\frac{B}{p^m}\right\rfloor\right) f(C)} \end{aligned} \]

第二个式子计算方式和type=0差不多，第一个式子只需要预处理 $ i^i $ 的前缀积即可。

type=2

\[\begin{aligned} &\prod\limits_{i=1}^A\prod\limits_{j=1}^B\prod\limits_{k=1}^Ci^{\gcd(i,j,k)}\\ =&\prod\limits_{d=1}^D\prod\limits_{i=1}^Ai^{\sum\limits_{j=1}^B\sum\limits_{k=1}^Cd[\gcd(i,j,k=d)]}&令D=\min(A,B,C),然后枚举\gcd\\ =&\prod\limits_{d=1}^D\prod\limits_{i=1}^{\left\lfloor\frac{A}{d}\right\rfloor}i^{\sum\limits_{j=1}^{\left\lfloor\frac{B}{d}\right\rfloor}\sum\limits_{k=1}^{\left\lfloor\frac{C}{d}\right\rfloor}d[\gcd(i,j,k=1)]}\\ =&\prod\limits_{d=1}^D\prod\limits_{i=1}^{\left\lfloor\frac{A}{d}\right\rfloor}(id)^{\sum\limits_{j=1}^{\left\lfloor\frac{B}{d}\right\rfloor}\sum\limits_{k=1}^{\left\lfloor\frac{C}{d}\right\rfloor}d\sum\limits_{t|\gcd(i,j,k)}\mu(t)}&莫比乌斯反演\\ =&\prod\limits_{d=1}^D\prod\limits_{t=1}^{\left\lfloor\frac{D}{d}\right\rfloor}\prod\limits_{i=1}^{\left\lfloor\frac{A}{dt}\right\rfloor}(idt)^{d\mu(t)\left\lfloor\frac{B}{dt}\right\rfloor\left\lfloor\frac{C}{dt}\right\rfloor}&将t提前\\ =&\prod\limits_{T=1}^D\prod\limits_{i=1}^{\left\lfloor\frac{A}{T }\right\rfloor}(iT)^{\left\lfloor\frac{B}{T}\right\rfloor\left\lfloor\frac{C}{T}\right\rfloor\sum\limits_{d|T}d\mu\left(\frac{T}{d}\right)}&枚举T=dt\\ =&\prod\limits_{T=1}^D\prod\limits_{i=1}^{\left\lfloor\frac{A}{T }\right\rfloor}(iT)^{\left\lfloor\frac{B}{T}\right\rfloor\left\lfloor\frac{C}{T}\right\rfloor\varphi(T)}&id*\mu=\varphi\\ =&\left(\prod\limits_{T=1}^D\left(\left\lfloor\frac{A}{T}\right\rfloor!\right)^{\left\lfloor\frac{B}{T}\right\rfloor\left\lfloor\frac{C}{T}\right\rfloor\varphi(T)}\right)\times\left(\prod\limits_{T=1}^DT^{\varphi(T)\left\lfloor\frac{A}{T}\right\rfloor\left\lfloor\frac{B}{T}\right\rfloor\left\lfloor\frac{C}{T}\right\rfloor}\right) \end{aligned} \]

\[\begin{aligned} &\prod\limits_{i=1}^A\prod\limits_{j=1}^B\prod\limits_{k=1}^C\gcd(i,j)^{\gcd(i,j,k)}\\ =&\prod\limits_{d=1}^D\prod\limits_{i=1}^{\left\lfloor\frac{A}{d}\right\rfloor}\prod\limits_{j=1}^{\left\lfloor\frac{B}{d}\right\rfloor}(\gcd(i,j)d)^{d\sum\limits_{k=1}^C[\gcd(i,j,k)=1]}&枚举\gcd(i,j,k)\\ =&\prod\limits_{d=1}^D\prod\limits_{i=1}^{\left\lfloor\frac{A}{d}\right\rfloor}\prod\limits_{j=1}^{\left\lfloor\frac{B}{d}\right\rfloor}(\gcd(i,j)d)^{d\sum\limits_{k=1}^C\sum\limits_{t|\gcd(i,j,k)}\mu(t)}\\ =&\prod\limits_{d=1}^D\prod\limits_{t=1}^{\left\lfloor\frac{D}{d}\right\rfloor}\prod\limits_{i=1}^{\left\lfloor\frac{A}{td}\right\rfloor}\prod\limits_{j=1}^{\left\lfloor\frac{B}{td}\right\rfloor}(\gcd(i,j)td)^{d\mu(t)\left\lfloor\frac{C}{td}\right\rfloor}\\ =&\prod\limits_{T=1}^D\prod\limits_{i=1}^{\left\lfloor\frac{A}{T}\right\rfloor}\prod\limits_{j=1}^{\left\lfloor\frac{B}{T}\right\rfloor}(\gcd(i,j)T)^{\left\lfloor\frac{C}{T}\right\rfloor\sum\limits_{d|T}d\mu\left(\frac{T}{d}\right)}\\ =&\prod\limits_{T=1}^D\prod\limits_{i=1}^{\left\lfloor\frac{A}{T}\right\rfloor}\prod\limits_{j=1}^{\left\lfloor\frac{B}{T}\right\rfloor}(\gcd(i,j)T)^{\left\lfloor\frac{C}{T}\right\rfloor\varphi(T)}&id*\mu=\varphi\\ =&\left(\prod\limits_{T=1}^DT^{\varphi(T)\left\lfloor\frac{A}{T}\right\rfloor\left\lfloor\frac{B}{T}\right\rfloor\left\lfloor\frac{C}{T}\right\rfloor}\right)\times\left(\prod\limits_{T=1}^D\prod\limits_{i=1}^{\left\lfloor\frac{A}{T}\right\rfloor}\prod\limits_{j=1}^{\left\lfloor\frac{B}{T}\right\rfloor}\gcd(i,j)^{\varphi(T)\left\lfloor\frac{C}{T}\right\rfloor}\right) \end{aligned} \]

然后你就会发现分子的右边的式子和分母的左边的式子约掉了。

于是我们现在只需要求 $ \prod\limits_{T=1}^ D\left(\left\lfloor\frac{A}{T}\right\rfloor!\right)^{\left\lfloor\frac{B}{T}\right\rfloor\left\lfloor\frac{C}{T}\right\rfloor\varphi(T)} $ 和 $ \prod\limits_{T=1}^ D\prod\limits_{i=1}^ {\left\lfloor\frac{A}{T}\right\rfloor}\prod\limits_{j=1}^ {\left\lfloor\frac{B}{T}\right\rfloor}\gcd(i,j)^{\varphi(T)\left\lfloor\frac{C}{T}\right\rfloor} $ 。

第一个式子只需要预处理阶乘、 $ \varphi $ 的前缀和，然后就可以分块。

第二个式子还需要推一推。

\[\begin{aligned} &\prod\limits_{T=1}^D\prod\limits_{i=1}^{\left\lfloor\frac{A}{T}\right\rfloor}\prod\limits_{j=1}^{\left\lfloor\frac{B}{T}\right\rfloor}\gcd(i,j)^{\varphi(T)\left\lfloor\frac{C}{T}\right\rfloor}\\ =&\prod\limits_{T=1}^D\left(\prod\limits_{d=1}^{\left\lfloor\frac{E}{T}\right\rfloor}d^{\sum\limits_{i=1}^{\left\lfloor\frac{A}{Td}\right\rfloor}\sum\limits_{j=1}^{\left\lfloor\frac{B}{Td}\right\rfloor}\sum\limits_{t|\gcd(i,j)}\mu(t)}\right)^{\varphi(T)\left\lfloor\frac{C}{T}\right\rfloor}&E=\min(A,B),枚举\gcd\\ =&\prod\limits_{T=1}^D\left(\prod\limits_{d=1}^{\left\lfloor\frac{E}{T}\right\rfloor}\prod\limits_{t=1}^{\left\lfloor\frac{E}{Td}\right\rfloor}d^{\mu(t)\left\lfloor\frac{A}{Ttd}\right\rfloor\left\lfloor\frac{B}{Ttd}\right\rfloor}\right)^{\varphi(T)\left\lfloor\frac{C}{T}\right\rfloor}\\ &\prod\limits_{T=1}^D\left(\prod\limits_{T'=1}^{\left\lfloor\frac{E}{T}\right\rfloor}\left(\prod\limits_{d|T'}d^{\mu\left(\frac{T'}{d}\right)}\right)^{\left\lfloor\frac{A}{TT'}\right\rfloor\left\lfloor\frac{B}{TT'}\right\rfloor}\right)^{\varphi(T)\left\lfloor\frac{C}{T}\right\rfloor} \end{aligned} \]

然后你会发现 $ \prod\limits_{T'=1}^ n\left(\prod\limits_{d|T'}d^{\mu\left(\frac{T'}{d}\right)}\right) $ 是可以预处理的。

于是乎，两遍整除分块就可以了。

最终时间复杂度是 $ O(n\log n+Tn^{\frac{3}{4}}\log n) $ 的。

代码：

#include
#include
#include
using namespace std;
using ll=long long;
inline int read()
{
    int s=0,w=1;char ch;
    while((ch=getchar())>'9'||ch<'0') if(ch=='-') w=-1;
    while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
    return s*w;
}
int mod;
ll qow(ll a,int b)
{
    b=(b%(mod-1)+mod-1)%(mod-1);
    a%=mod;
    ll ans=1;
    while(b)
    {
        if(b&1) ans=ans*a%mod;
        a=a*a%mod;
        b>>=1;
    }
    return ans;
}
mapjyh[100001];
ll prephi[100001];
int pri[100001];
bool is[100001];
int phi[100001];
int pm[100001];
int mu[100001];
ll jc1[100001];
ll jc2[100001];
ll d1[100001];
ll d2[100001];
int A,B,C;
inline ll f(int i){ return 1ll*i*(i+1)/2%(mod-1);}
inline ll get2(int A,int B)
{
    ll ans=jyh[A][B];
    if(ans) return ans;
    ans=1;
    int E=min(A,B);
    for(int lTp=1,rTp;lTp<=E;lTp=rTp+1)
    {
        rTp=min(A/(A/lTp),B/(B/lTp));
        ll val=d1[rTp]*d2[lTp-1]%mod;
        ans=ans*qow(val,(ll)(A/lTp)*(B/rTp)%(mod-1))%mod;
    }
    return jyh[A][B]=ans;
}
inline ll get1(int A,int B,int C)
{
    ll ans=1;
    int D=min(min(A,B),C);
    for(int lT=1,rT;lT<=D;lT=rT+1)
    {
        rT=min(min(A/(A/lT),B/(B/lT)),C/(C/lT));
        ans=ans*qow(get2(A/lT,B/lT),(prephi[rT]-prephi[lT-1])%(mod-1)*(C/lT)%(mod-1))%mod
               *qow(get2(A/lT,C/lT),(prephi[rT]-prephi[lT-1])%(mod-1)*(B/lT)%(mod-1))%mod;
    }
    return ans;
}
inline ll get3(int A,int B,int C)
{
    ll ans=1;
    for(int lT=1,rT;lT<=A&&lT<=B&&lT<=C;lT=rT+1)
    {
        rT=min(min(A/(A/lT),B/(B/lT)),C/(C/lT));
        ans=ans*qow(jc1[A/lT],(prephi[rT]-prephi[lT-1])%(mod-1)*(B/lT)*(C/lT)%(mod-1))%mod;
    }
    return ans;
}
int main()
{
    int t=read(),n=100000;mod=read();
    mu[1]=phi[1]=1;
    for(int i=2;i<=n;i++)
    {
        if(!is[i]) pri[++pri[0]]=i,mu[i]=-1,phi[i]=i-1;
        for(int j=1;j<=pri[0]&&i*pri[j]<=n;j++)
        {
            is[i*pri[j]]=1;
            if(i%pri[j]==0)
            {
                phi[i*pri[j]]=phi[i]*pri[j];
                break;
            }
            mu[i*pri[j]]=-mu[i];
            phi[i*pri[j]]=phi[i]*(pri[j]-1);
        }
    }
    for(int i=1;i<=pri[0];i++) for(ll j=pri[i];j<=n;j*=pri[i]) pm[j]=pri[i];
    jc1[0]=jc2[0]=d1[0]=d2[0]=1;
    for(int i=1;i<=n;i++)
    {
        d1[i]=1;
        prephi[i]=prephi[i-1]+phi[i];
        jc1[i]=jc1[i-1]*i%mod;
        jc2[i]=jc2[i-1]*qow(i,i)%mod;
    }
    for(int i=1;i<=n;i++) for(int j=i;j<=n;j+=i)
        d1[j]=d1[j]*qow(i,mu[j/i])%mod;
    for(int i=2;i<=n;i++) d1[i]=(d1[i]*d1[i-1])%mod;
    for(int i=1;i<=n;i++) d2[i]=qow(d1[i],mod-2);
    while(t--)
    {
        A=read(),B=read(),C=read();
        ll ans=1,val=1;



        ans=ans*qow(jc1[A],1ll*B*C%(mod-1))%mod;
        ans=ans*qow(jc1[B],1ll*A*C%(mod-1))%mod;
        for(int i=1;i<=A&&i<=B;i++) if(pm[i])
            val=val*qow(pm[i],1ll*(A/i)*(B/i)%(mod-1))%mod;
        val=qow(val,C);
        ans=ans*qow(val,mod-2)%mod,val=1;
        for(int i=1;i<=A&&i<=C;i++) if(pm[i])
            val=val*qow(pm[i],1ll*(A/i)*(C/i)%(mod-1))%mod;
        val=qow(val,B);
        ans=ans*qow(val,mod-2)%mod,val=1;
        printf("%lld ",ans),ans=1;



        ans=ans*qow(jc2[A],f(B)*f(C)%(mod-1))%mod;
        ans=ans*qow(jc2[B],f(A)*f(C)%(mod-1))%mod;
        for(int i=1;i<=A&&i<=B;i++) if(pm[i])
            val=val*qow(pm[i],f(A/i)*f(B/i)%(mod-1)*i%(mod-1)*i%(mod-1))%mod;
        val=qow(val,f(C));
        ans=ans*qow(val,mod-2)%mod,val=1;
        for(int i=1;i<=A&&i<=C;i++) if(pm[i])
            val=val*qow(pm[i],f(A/i)*f(C/i)%(mod-1)*i%(mod-1)*i%(mod-1))%mod;
        val=qow(val,f(B));
        ans=ans*qow(val,mod-2)%mod,val=1;
        printf("%lld ",ans),ans=1;



        ans=qow(get1(A,B,C),mod-2);
        ans=ans*get3(A,B,C)%mod*get3(B,A,C)%mod;
        printf("%lld\n",ans);
    }
    return 0;
}
题解莫比乌斯反演数论分块数学

相关

洛谷P5340 大中锋的游乐场 题解 分层图最短路

Ubuntu 断网问题解决

[SQL] SQL Server 2019 中LocalDB 报错的问题解决

题解 Count on a tree II/【模板】树分块

HttpURLConnection发送中文乱码问题解决

1675: [Usaco2005 Feb]Rigging the Bovine Election 竞选划区（题解第一弹）

P7715 「EZEC-10」Shape 题解

Proguard混淆之后行数LineNumber对不上问题解决

ZYNQ xilinx_axienet CPU软中断占用过高问题解决记录

题解 P6345 [CCO 2017]接雨滴

魔咒词典 - 题解【暴搜】

最大数maxnumber - 题解【树状数组】

标签