Luogu5518 幽灵乐团

题面

简化题意

给定三个数 $A,B,C$，求 $p$ 分别为 $1,ijk,\gcd(i,j,k)$ 时，下面式子的值：

$\prod_{i=1}^A \prod_{j=1}^B \prod_{k=1}^C \left( \frac{\rm{lcm}(i,j)}{\gcd(i,j)} \right)^p$

多测，对大质数取模。$T=70,A,B,C\leq 10^5$。

题解

本题具有巨量推长而复杂的式子环节。请谨慎阅读。

显然，$\operatorname{lcm}(a,b) = \frac{ab}{\gcd(a,b)}$，于是题目转化为：

$\prod_{i=1}^A \prod_{j=1}^B \prod_{k=1}^C \left( \frac{ij}{\gcd(i,j)\gcd(i,k)} \right)^p$

于是可以拆分为两个子问题做：

$F(A,B,C)=\prod_{i=1}^A \prod_{j=1}^B \prod_{k=1}^C i^p$

这个当分子。

$G(A,B,C) = \prod_{i=1}^A \prod_{j=1}^B \prod_{k=1}^C \gcd(i,j)^p$

这个当分母。于是：

$ans = \frac{F(A,B,C)F(B,A,C)}{G(A,B,C)G(A,C,B)}$

于是就可以分别讨论了。下面按照 $p$ 的取值分三种情况讨论：

情况一

$p=1$ 的情况：

分子

这个太显然了。

$F(A,B,C) = \prod_{i=1}^A \prod_{j=1}^B \prod_{k=1}^C i = (A!)^{BC}$

预处理阶乘后，单次询问复杂度 $\mathcal O(\log n)$。

分母

$G(A,B,C) = \left(\prod_{i=1}^A \prod_{j=1}^B \gcd(i,j)\right)^C$

莫比乌斯反演：

$\left( \prod_{d=1}^{\min(A,B)} d^{ \sum_{i=1}^{\left\lfloor{\frac{A}{d}}\right\rfloor} \sum_{j=1}^{\left\lfloor{\frac{B}{d}}\right\rfloor } [\gcd(i,j)=1] } \right)^C$

上面那个指数我们拿出来考虑一下，还是反演：

$\sum_{i=1}^{\left\lfloor{\frac{A}{d}}\right\rfloor} \sum_{j=1}^{\left\lfloor{\frac{B}{d}}\right\rfloor} \sum_{p\mid\gcd(i,j)} \mu(p)$

这玩意太水了，不难得到：

$\sum_{p=1}^{\min(\left\lfloor{\frac{A}{d}}\right\rfloor,\left\lfloor{\frac{B}{d}}\right\rfloor)} \mu(p) \left\lfloor{\frac{A}{dp}}\right\rfloor\left\lfloor{\frac{B}{dp}}\right\rfloor$

因此原式为：

$\left(\prod_{d=1}^{\min(A,B)} d^{ \sum_{p=1}^{\min(\left\lfloor{\frac{A}{d}}\right\rfloor,\left\lfloor{\frac{B}{d}}\right\rfloor)} \mu(p) \left\lfloor{\frac{A}{dp}}\right\rfloor\left\lfloor{\frac{B}{dp}}\right\rfloor } \right)^C$

太丑了，把指数的求和号拆出来，换个元：

$\left[ \prod_{p=1}^{\min(A,B)} \left( \prod_{d\mid p} d^{\mu(\frac{p}{d})} \right) ^ {\left\lfloor{\frac{A}{p}}\right\rfloor\left\lfloor{\frac{B}{p}}\right\rfloor} \right]^C$

于是设：

$f(n) = \prod_{d\mid n} d^{\mu(\frac{n}{d})}$

那么原式可以变为：

$\left( \prod_{p=1}^{\min(A,B)} f(p) ^ {\left\lfloor{\frac{A}{p}}\right\rfloor\left\lfloor{\frac{B}{p}}\right\rfloor} \right)^C$

预处理 $f$ 可以用埃式筛，再预处理 $f$ 的前缀积，询问时整除分块。单次询问复杂度 $\mathcal O(\sqrt{n}\log n)$。

情况二

$p=i\times j\times k$ 的情况：

分子

$F(A,B,C) = \prod_{i=1}^A i ^ {i\times \frac{B(B+1)}{2}\times \frac{C(C+1)}{2}}$

预处理 $\prod i^i$ 即可，单次询问 $\mathcal O(\log n)$。

分母

提出指数，然后反演得到：

$G(A,B,C) = \left( \prod_{d=1}^{\min(A,B)} d^{ \sum_{i=1}^{\left\lfloor{\frac{A}{d}}\right\rfloor} \sum_{j=1}^{\left\lfloor{\frac{B}{d}}\right\rfloor} id\times jd [\gcd(i,j)=1] } \right) ^ {\frac{C(C+1)}{2}}$

然后把指数拉出来莫比乌斯反演：

$d^2 \sum_{i=1}^{\left\lfloor{\frac{A}{d}}\right\rfloor} \sum_{j=1}^{\left\lfloor{\frac{B}{d}}\right\rfloor} ij \sum_{p\mid\gcd(i,j)} \mu(p)$

套路性换一下顺序：

$= d^2 \sum_{p=1}^{\min(\left\lfloor{\frac{A}{d}}\right\rfloor,\left\lfloor{\frac{B}{d}}\right\rfloor)} p^2\mu(p) \sum_{i=1}^{\left\lfloor{\frac{A}{dp}}\right\rfloor} i \sum_{j=1}^{\left\lfloor{\frac{B}{dp}}\right\rfloor} j$

然后放回去：

$\left( \prod_{d=1}^{\min(A,B)} d ^ { d^2 \sum_{p=1}^{\min(\left\lfloor{\frac{A}{d}}\right\rfloor,\left\lfloor{\frac{B}{d}}\right\rfloor)} p^2\mu(p) \frac{\left\lfloor{\frac{A}{dp}}\right\rfloor(\left\lfloor{\frac{A}{dp}}\right\rfloor+1)}{2} \frac{\left\lfloor{\frac{B}{dp}}\right\rfloor(\left\lfloor{\frac{B}{dp}}\right\rfloor+1)}{2} } \right) ^ {\frac{C(C+1)}{2}}$

把前面这依托 $\sum$ 里的东西修一下：

$\left[ \prod_{p=1}^{\min(A,B)} \left( \prod_{d\mid p} d^{ p^2\mu(\frac{p}{d})} \right) ^ {\frac{\left\lfloor\frac{A}{p}\right\rfloor(\left\lfloor\frac{A}{p}\right\rfloor+1)}{2}\times \frac{\left\lfloor\frac{B}{p}\right\rfloor(\left\lfloor\frac{B}{p}\right\rfloor+1)}{2}} \right] ^ {\frac{C(C+1)}{2}}$

于是得到了一个很复杂的式子，设：

$f(n) = \prod_{d\mid n} d^ {n^2 \mu(\frac{n}{d})}$

那么原式可以变为：

$\left[ \prod_{p=1}^{\min(A,B)} f(p) ^ {\frac{\left\lfloor\frac{A}{p}\right\rfloor(\left\lfloor\frac{A}{p}\right\rfloor+1)}{2}\times \frac{\left\lfloor\frac{B}{p}\right\rfloor(\left\lfloor\frac{B}{p}\right\rfloor+1)}{2}} \right] ^ {\frac{C(C+1)}{2}}$

预处理 $f$ 仍然可以埃式筛，然后预处理它的前缀积，这个式子就可以用整除分块求。单次询问复杂度 $\mathcal O(\sqrt{n}\log n)$。

情况三

正片开始。

$p=\gcd(i,j,k)$ 的情况：

分子

$F(A,B,C) = \prod_{d=1}^{\min(A,B,C)} \prod_{i=1}^A i ^ {\sum_{j=1}^B \sum_{k=1}^C [\gcd(i,j,k)=d]}$

感到无从下手？把 $i$ 直接变成 $\frac{i}{d}$：

$\prod_{d=1}^{\min(A,B,C)} \prod_{i=1}^{\left\lfloor\frac{A}{d}\right\rfloor} (id) ^ { d \sum_{j=1}^{\left\lfloor\frac{B}{d}\right\rfloor} \sum_{k=1}^{\left\lfloor\frac{C}{d}\right\rfloor} [\gcd(i,j,k) = 1] }$

还是先考虑指数：

$d \sum_{j=1}^{\left\lfloor\frac{B}{d}\right\rfloor} \sum_{k=1}^{\left\lfloor\frac{C}{d}\right\rfloor} [\gcd(i,j,k) = 1]$

三个数的 $\gcd$ 暴力莫反就有点恶心了：

$d \sum_{j=1}^{\left\lfloor\frac{B}{d}\right\rfloor} \sum_{k=1}^{\left\lfloor\frac{C}{d}\right\rfloor} \sum_{t\mid\gcd(i,j,k)} \mu(t)$

交换求和号的时候，注意 $t$ 需要同时满足能整除 $i,j,k$：

$\sum_{t=1}^{\min(\left\lfloor\frac{A}{d}\right\rfloor,\left\lfloor\frac{B}{d}\right\rfloor,\left\lfloor\frac{C}{d}\right\rfloor)} d \mu(t) [t\mid i] \sum_{j=1}^{\left\lfloor\frac{B}{d}\right\rfloor} [t\mid j] \sum_{k=1}^{\left\lfloor\frac{C}{d}\right\rfloor} [t\mid k]$

没什么思路？把枚举 $t$ 的求和号移到指数下面变成连乘号：

$\prod_{d=1}^{\min(A,B,C)} \prod_{t=1}^{\min(\left\lfloor\frac{A}{d}\right\rfloor,\left\lfloor\frac{B}{d}\right\rfloor,\left\lfloor\frac{C}{d}\right\rfloor)} \prod_{i=1}^{\left\lfloor\frac{A}{td}\right\rfloor} (itd) ^ {d\mu(t) \left\lfloor\frac{B}{td}\right\rfloor\left\lfloor\frac{C}{td}\right\rfloor}$

抽个 $p$ 出来换元：

$\prod_{p=1}^{\min(A,B,C)} \prod_{d\mid p} \prod_{i=1}^{\left\lfloor\frac{A}{p}\right\rfloor} (ip) ^ {d\mu(\frac{p}{d}) \left\lfloor\frac{B}{p}\right\rfloor\left\lfloor\frac{C}{p}\right\rfloor}$

再把第三个 $\prod$ 搞一下呗：

$\prod_{p=1}^{\min(A,B,C)} \left[ \prod_{d\mid p} \left( p^{\left\lfloor\frac{A}{p}\right\rfloor} \prod_{i=1}^{\left\lfloor\frac{A}{p}\right\rfloor} i \right) ^ {d\mu(\frac{p}{d})} \right] ^ {\left\lfloor\frac{B}{p}\right\rfloor\left\lfloor\frac{C}{p}\right\rfloor}$

然后你发现这个指数还可以换一换：

$\prod_{p=1}^{\min(A,B,C)} \left[ \left( p^{\left\lfloor\frac{A}{p}\right\rfloor} \prod_{i=1}^{\left\lfloor\frac{A}{p}\right\rfloor} i \right) ^ {\sum_{d\mid p} d\mu(\frac{p}{d})} \right] ^ {\left\lfloor\frac{B}{p}\right\rfloor\left\lfloor\frac{C}{p}\right\rfloor}$

仔细观察现在的指数，是狄利克雷卷积 $\operatorname{id} \ast \mu = \varphi$：

$\prod_{p=1}^{\min(A,B,C)} \left[ \left( p^{\left\lfloor\frac{A}{p}\right\rfloor} \prod_{i=1}^{\left\lfloor\frac{A}{p}\right\rfloor} i \right) ^ {\varphi(p)} \right] ^ {\left\lfloor\frac{B}{p}\right\rfloor\left\lfloor\frac{C}{p}\right\rfloor}$

后面的转化就相对常规了：

$\prod_{p=1}^{\min(A,B,C)} \left[ p^{\left\lfloor\frac{A}{p}\right\rfloor\varphi(p)} \left( \prod_{i=1}^{\left\lfloor\frac{A}{p}\right\rfloor} i \right) ^ {\varphi(p)} \right] ^ {\left\lfloor\frac{B}{p}\right\rfloor\left\lfloor\frac{C}{p}\right\rfloor}$

显然需要预处理阶乘，然后设：

$f(n) = n^{\varphi(n)}$

线性筛欧拉函数后可以 $n\log n$ 预处理出来。那么原式可以写为：

$\prod_{p=1}^{\min(A,B,C)} f(p)^{\left\lfloor\frac{A}{p}\right\rfloor\left\lfloor\frac{B}{p}\right\rfloor\left\lfloor\frac{C}{p}\right\rfloor} f(\left\lfloor\tfrac{A}{p}\right\rfloor!) ^ {\left\lfloor\frac{B}{p}\right\rfloor\left\lfloor\frac{C}{p}\right\rfloor}$

整除分块即可，单次询问 $\mathcal O(\sqrt{n}\log n)$。

分母

$G(A,B,C) = \prod_{d=1}^{\min(A,B,C)} \prod_{i=1}^A \prod_{j=1}^B \prod_{k=1}^C d^{\gcd(d,k)} [\gcd(i,j)=d]$

套路性再反演一下：

$\prod_{d=1}^{\min(A,B,C)} \left( d ^ {\sum_{i=1}^A \sum_{j=1}^B [\gcd(i,j)=d]} \right) ^ {\sum_{k=1}^C \gcd(d,k)}$

先考虑最外面的指数吧：

$\sum_{k=1}^C \gcd(d,k)$

用欧拉反演 $\operatorname{id} = \varphi\ast 1$：

$= \sum_{k=1}^C \sum_{t\mid\gcd(d,k)} \varphi(t) = \sum_{t\mid d} \varphi(t) \left\lfloor\frac{C}{t}\right\rfloor$

然后我们考虑里面那个指数：

$\sum_{i=1}^A \sum_{j=1}^B [\gcd(i,j)=d]$

我们发现，这和情况一的分母部分形式是一样的，这里不赘述：

$\sum_{i=1}^A \sum_{j=1}^B [\gcd(i,j)=d] = \sum_{g=1}^{\min(A,B)} \mu(g) \left\lfloor\frac{A}{gd}\right\rfloor\left\lfloor\frac{B}{gd}\right\rfloor$

于是就可以看看原式变成了什么：

$\prod_{d=1}^{\min(A,B,C)} d ^ {\left(\sum_{g=1}^{\min(A,B)} \mu(g) \left\lfloor\frac{A}{gd}\right\rfloor\left\lfloor\frac{B}{gd}\right\rfloor\right) \times \left( \sum_{t\mid d} \varphi(t) \left\lfloor\frac{C}{t}\right\rfloor \right) }$

我们发现，如果预处理 $f(d) = \sum_{g=1}^{\min(A,B)} \mu(g) \left\lfloor\frac{A}{gd}\right\rfloor\left\lfloor\frac{B}{gd}\right\rfloor$，这个式子可以单次询问 $\mathcal O(n\log n)$ 完成。如果常数够小的话这个题就做出来了。

当然并不是所有人常数都和 vv 一样小，所以这并不好。

更优的做法

重新考虑这个情况：

$\prod_{i=1}^A \prod_{j=1}^B \prod_{k=1}^C \left( \frac{\operatorname{lcm}(i,j)}{\gcd(i,k)} \right) ^ {\gcd(i,j,k)}$

我们对其求 $\ln$，把乘法转加法，指数转系数：

$\sum_{i=1}^A \sum_{j=1}^B \sum_{k=1}^C \gcd(i,j,k) \ln \left( \frac{\operatorname{lcm}(i,j)}{\gcd(i,k)} \right)$

于是就可以常规反演了，套路和前面一样就不多赘述：

$\sum_{d=1}^{\min(A,B,C)} \varphi(d) \sum_{i=1}^{\left\lfloor\frac{A}{d}\right\rfloor} \sum_{j=1}^{\left\lfloor\frac{B}{d}\right\rfloor} \sum_{k=1}^{\left\lfloor\frac{C}{d}\right\rfloor} \ln(\frac{\operatorname{lcm}(i,j)}{\gcd(i,k)})$

然后我们把它 $\exp$ 回来：

$\prod_{d=1}^{\min(A,B,C)} \left( \prod_{i=1}^{\left\lfloor\frac{A}{d}\right\rfloor} \prod_{j=1}^{\left\lfloor\frac{B}{d}\right\rfloor} \prod_{k=1}^{\left\lfloor\frac{C}{d}\right\rfloor} \frac{\operatorname{lcm}(i,j)}{\gcd(i,k)} \right)^{\varphi(d)}$

括号里面的东西和情况一是一样的。预处理欧拉函数和前缀和，单次询问 $\mathcal O(\sqrt{n}\log n)$。

代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int max_n=200005,N=200000;int mod;
inline int read(){
    int x=0;bool w=0;char c=getchar();
    while(c<'0' || c>'9') w|=c=='-',c=getchar();
    while(c>='0' && c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();
    return w?-x:x;
}
inline void write(int x){
    if(x<0) putchar('-'),x=-x;
    if(x>9) write(x/10);
    putchar(x%10^48);
}
inline int mi(int a,int p=mod-2){
    int res=1;
    a=(a%mod+mod)%mod,p%=mod-1;
    while(p){
        if(p&1) res*=a,res%=mod;
        a*=a,a%=mod,p>>=1;
    }
    return res;
}

bool isp[max_n];
int pr[max_n],cntp,mu[max_n],phi[max_n];

inline void Init(int n){
    memset(isp,1,sizeof(isp)),isp[1]=0;
    mu[1]=phi[1]=1;
    for(register int i=2;i<=n;++i){
        if(isp[i]){
            pr[++cntp]=i;
            mu[i]=-1,
            phi[i]=i-1;
        }
        for(register int j=1;j<=cntp && i*pr[j]<=n;++j){
            isp[i*pr[j]]=0;
            if(i%pr[j]==0){
                mu[i*pr[j]]=0,
                phi[i*pr[j]]=phi[i]*pr[j];
                break;
            }
            mu[i*pr[j]]=-mu[i],
            phi[i*pr[j]]=phi[i]*phi[pr[j]];
        }
    }
}

int A,B,C,fac[max_n],iv[max_n];

namespace TP1{
    int f[max_n],inv[max_n];
    inline void init(int n){
        f[0]=inv[0]=1;
        for(register int i=0;i<=n;++i)
            f[i]=1;
        for(register int i=1;i<=n;++i)
            for(register int j=i,k=1;j<=n;j+=i,++k)
                if(mu[k]!=0){
                    if(mu[k]>0)
                        f[j]*=i;
                    else
                        f[j]*=iv[i];
                    f[j]%=mod;
                }
        for(register int i=1;i<=n;++i){
            f[i]=f[i-1]*f[i]%mod,
            inv[i]=mi(f[i]);
        }
    }
    inline int F(int A,int B,int C){
        return mi(fac[A],B*C);
    }
    inline int G(int A,int B,int C){
        int res=1,up=min(A,B);
        for(register int l=1,r;l<=up;l=r+1){
            r=min(A/(A/l),B/(B/l));
            res=res*mi(f[r]*inv[l-1],(A/l)*(B/l))%mod;
        }
        return mi(res,C);
    }
    inline int sol(int A,int B,int C){
        int fz=F(A,B,C)*F(B,A,C)%mod,fm=G(A,B,C)*G(A,C,B)%mod;
        return fz*mi(fm)%mod;
    }
}

namespace TP2{
    int f[max_n],g[max_n],inv[max_n];
    inline void init(int n){
        f[0]=g[0]=inv[0]=1;
        for(register int i=1;i<=n;++i){
            f[i]=f[i-1]*mi(i,i)%mod,
            g[i]=g[i-1]*mi(TP1::f[i]*TP1::inv[i-1],i*i)%mod,
            inv[i]=mi(g[i]);
        }
    }
    inline int Sum(int x){
        return x*(x+1)/2%(mod-1);
    }
    inline int F(int A,int B,int C){
        return mi(f[A],Sum(B)*Sum(C));
    }
    inline int G(int A,int B,int C){
        int res=1,up=min(A,B);
        for(register int l=1,r;l<=up;l=r+1){
            r=min(A/(A/l),B/(B/l));
            res=res*mi(g[r]*inv[l-1],Sum(A/l)*Sum(B/l))%mod;
        }
        return mi(res,Sum(C));
    }
    inline int sol(int A,int B,int C){
        int fz=F(A,B,C)*F(B,A,C)%mod,fm=G(A,B,C)*G(A,C,B)%mod;
        return fz*mi(fm)%mod;
    }
}

namespace TP3{
    int f[max_n];
    inline void init(int n){
        f[1]=1;
        for(register int i=2;i<=n;++i)
            f[i]=(f[i-1]+phi[i])%(mod-1);
    }
    inline int sol(int A,int B,int C){
        int res=1,up=min(A,min(B,C));
        for(register int l=1,r;l<=up;l=r+1){
            r=min(A/(A/l),min(B/(B/l),C/(C/l)));
            res=res*mi(TP1::sol(A/l,B/l,C/l),f[r]-f[l-1]+mod-1)%mod;
        }
        return res;
    }
}

signed main(){
//  freopen(".in","r",stdin),
//  freopen(".out","w",stdout);
    int T=read();mod=read();
    fac[0]=1;
    for(register int i=1;i<=N;++i)
        fac[i]=fac[i-1]*i%mod;
    for(register int i=0;i<=N;++i)
        iv[i]=mi(i);
    Init(N),
    TP1::init(N),
    TP2::init(N),
    TP3::init(N);
    while(T--){
        int A=read(),B=read(),C=read();
        write(TP1::sol(A,B,C)),putchar(' ');
        write(TP2::sol(A,B,C)),putchar(' ');
        write(TP3::sol(A,B,C)),putchar('\n');
    }
    return 0;
}

附记

他（CYJian）还给你们讲了幽灵乐团？？这个人有病吧。

—— CZZ

这完全是拖时间才给你们讲这个吧？

—— HJS