题解 P5518 【[MtOI2019]幽灵乐团 / 莫比乌斯反演基础练习题】
灵乌路空
2020-11-15 07:45:42
更好的阅读体验：[我的 Blog](https://www.cnblogs.com/luckyblock/p/13975070.html)。
扯一句，题面里将露娜萨（Lunasa）误写成了 Lusana，不人气姐妹连名字都不配拥有（
## 简述
原题面：[Luogu](https://www.luogu.com.cn/problem/P5518)
>给定参数 $p$，有 $T$ 组数据，每次给定参数 $A,B,C$，求：
>$$\prod_{i=1}^{A}\prod_{j=1}^{B}\prod_{k=1}^{C}\left(\dfrac{\operatorname{lcm}(i,j)}{\gcd(i,k)}\right)^{f(type)}\pmod p$$
>其中 $f(type)$ 的取值如下：
>$$f(type) = \begin{cases}
1 &type = 0\\
i\times j\times k &type = 1\\
\gcd(i,j,k) &type = 2
\end{cases}$$
>$1\le A,B,C\le 10^5$，$10^7\le p\le 1.05\times 10^9$，$p\in \mathbb{P}$，$T=70$。
>2.5S，128MB。
## 分析
### 原式
先化下原式，原式等于：
$$\prod_{i=1}^{A}\prod_{j=1}^{B}\prod_{k=1}^{C}\left(\dfrac{i\times j }{\gcd(i,j)\times \gcd(i,k)}\right)^{f(type)}$$
发现每一项仅与两个变量有关，设：
$$\begin{aligned}
f_1(a,b,c) &= \prod_{i=1}^{a}\prod_{j=1}^{b}\prod_{k=1}^{c} i^{f(type)}\\
f_2(a,b,c) &= \prod_{i=1}^{a}\prod_{j=1}^{b}\prod_{k=1}^{c} \gcd(i,j)^{f(type)}
\end{aligned}$$
发现 $\prod$ 可以随意交换，则原式等价于：
$$\dfrac{f_1(a,b,c)\times f_1(b,a,c)}{f_2(a,b,c)\times f_2(a,c,b)}$$
考虑在 $type$ 取值不同时，如何快速求得 $f_1$ 与 $f_2$。
一共有 $6$ 个需要推导的式子，不妨就叫它们 $1\sim 6$ 面了（
---
### type = 0
$$\begin{aligned}
f_1(a,b,c) &= \prod_{i=1}^{a}\prod_{j=1}^{b}\prod_{k=1}^{c} i\\
f_2(a,b,c) &= \prod_{i=1}^{a}\prod_{j=1}^{b}\prod_{k=1}^{c} \gcd(i,j)
\end{aligned}$$
对于 1 面，显然有：
$$\prod_{i=1}^{a}\prod_{j=1}^{b}\prod_{k=1}^{c} i = \left(\prod_{i=1}^{a}i\right)^{b\times c}$$
预处理阶乘 + 快速幂即可，单次计算时间复杂度 $O(\log n)$。
---
再考虑 2 面，套路地枚举 $\gcd$，显然有：
$$\large \begin{aligned}
&\prod_{i=1}^{a}\prod_{j=1}^{b}\prod_{k=1}^{c} \gcd(i,j)\\
=&\left(\prod_{i=1}^{a}\prod_{j=1}^{b}\gcd(i,j)\right)^c\\
=& \left(\prod_{d=1} d^{\left(\sum\limits_{i=1}^{a}\sum\limits_{j=1}^{b}[\gcd(i,j) = d]\right)}\right)^c
\end{aligned}$$
指数是个套路，可以看这里：[P3455 [POI2007]ZAP-Queries](https://www.luogu.com.cn/problem/P3455)。于是有：
$$\begin{aligned}
&\sum\limits_{i=1}^{a}\sum\limits_{j=1}^{b}[\gcd(i,j) = d]\\
=& \sum\limits_{i=1}^{\left\lfloor\frac{a}{d}\right\rfloor}\sum\limits_{j=1}^{\left\lfloor\frac{b}{d}\right\rfloor}[\gcd(i,j) = 1]\\
=& \sum\limits_{i=1}^{\left\lfloor\frac{a}{d}\right\rfloor}\sum\limits_{j=1}^{\left\lfloor\frac{b}{d}\right\rfloor}\sum_{k\mid \gcd(i,j)}\mu (k)\\
=& \sum_{k=1}\mu(k)\left\lfloor\dfrac{a}{kd}\right\rfloor\left\lfloor\dfrac{b}{kd}\right\rfloor
\end{aligned}$$
代回原式，略做处理，则原式等于：
$$\large \begin{aligned}
&\left(\prod_{d=1} d^{\left(\sum\limits_{k=1}\mu(k)\left\lfloor\frac{a}{kd}\right\rfloor\left\lfloor\frac{b}{kd}\right\rfloor\right)}\right)^c\\
=& \left(\prod_{d=1} \left(d^{\sum\limits_{k=1}\mu(k)}\right)^{\left\lfloor\frac{a}{kd}\right\rfloor\left\lfloor\frac{b}{kd}\right\rfloor}\right)^c\\
=& \prod_{d=1} \left(\prod_{k=1}^{\left\lfloor\frac{n}{d}\right\rfloor}d^{\left(\mu(k)\left\lfloor\frac{a}{kd}\right\rfloor\left\lfloor\frac{b}{kd}\right\rfloor\right)}\right)^c
\end{aligned}$$
像[「SDOI2017」数字表格](https://www.cnblogs.com/luckyblock/p/13966454.html) 一样，考虑枚举 $t=kd$ 和 $d$，则原式等于：
$$\large \prod_{t=1}^{n}\left(\left(\prod_{d|t} d^{\mu{\left(\frac{t}{d}\right)}}\right)^{\left\lfloor\frac{a}{t}\right\rfloor\left\lfloor\frac{b}{t}\right\rfloor}\right)^c$$
设：
$$\large g_0(t) = \prod_{d|t}d^{\mu\left(\frac{t}{d}\right)}$$
线性筛预处理 $\mu$ 后，$g_0(t)$ 可以用埃氏筛预处理，时间复杂度 $O(n\log n)$。再代回原式，原式等于：
$$\large \prod_{t=1}^{a}\left(g_0(t)^{\left\lfloor\frac{a}{t}\right\rfloor\left\lfloor\frac{b}{t}\right\rfloor}\right)^c$$
预处理 $g_0(t)$ 的前缀积和前缀积的逆元，复杂度 $O(n\log n)$。
数论分块 + 快速幂计算即可，单次时间复杂度 $O(\sqrt n\log n)$。
---
### type = 1
$$\begin{aligned}
f_1(a,b,c) &= \prod_{i=1}^{a}\prod_{j=1}^{b}\prod_{k=1}^{c} i^{i\times j\times k}\\
f_2(a,b,c) &= \prod_{i=1}^{a}\prod_{j=1}^{b}\prod_{k=1}^{c} \gcd(i,j)^{i\times j\times k}
\end{aligned}$$
考虑 3 面，把 $\prod k$ 扔到指数位置，有：
$$\large \prod_{i=1}^{a}\prod_{j=1}^{b}\prod_{k=1}^{c} i^{i\times j\times k} = \prod_{i=1}^{a}\prod_{j=1}^{b}i^{\left(i\times j\times \sum\limits_{k = 1}^{c} k\right)}$$
再把 $\prod j$ 也扔到指数位置，引入 $\operatorname{sum}(n) = \sum_{i=1}^{n} i = \frac{n(n+1)}{2}$，原式等于：
$$\left(\prod_{i=1}^{a}i^i\right)^{\operatorname{sum}(b)\times \operatorname{sum}(c)}$$
预处理 $i^i$ 的前缀积，复杂度 $O(n\log n)$。
指数可以 $O(1)$ 算出，然后快速幂，单次时间复杂度 $O(\log n)$。
根据费马小定理，指数需要对 $p - 1$ 取模。注意 $p-1$ 不是质数，计算 $\operatorname{sum}$ 时不能用逆元，但乘不爆 `LL`，直接算就行。
---
再考虑 4 面，发现 $k$ 与 $\gcd$ 无关，则同样把 $\prod k$ 扔到指数位置，则有：
$$\large \begin{aligned}
&\prod_{i=1}^{a}\prod_{j=1}^{b}\prod_{k=1}^{c} \gcd(i,j)^{i\times j\times k}\\
=& \left(\prod_{i=1}^a\prod_{j=1}^b\gcd(i,j)^{i\times j}\right)^{\operatorname{sum}(c)}
\end{aligned}$$
套路地枚举 $\gcd$，原式等于：
$$\large \left(\prod_{d=1}d^{\left(\sum\limits_{i=1}^a \sum\limits_{j=1}^b i\times j[\gcd(i,j)=d]\right)}\right)^{\operatorname{sum}(c)}$$
大力化简指数，有：
$$\large \begin{aligned}
&\sum\limits_{i=1}^a \sum\limits_{j=1}^b i\times j[\gcd(i,j)=d]\\
=& d^2 \sum\limits_{i=1}^{\left\lfloor\frac{a}{d}\right\rfloor} \sum\limits_{j=1}^{\left\lfloor\frac{b}{d}\right\rfloor} i\times j[\gcd(i,j)=1\\
=& d^2 \sum\limits_{i=1}^{\left\lfloor\frac{a}{d}\right\rfloor} i \sum\limits_{j=1}^{\left\lfloor\frac{b}{d}\right\rfloor} j\sum\limits_{t|\gcd(i,j)}\mu(t)\\
=& d^2 \sum\limits_{i=1}^{\left\lfloor\frac{a}{d}\right\rfloor} i \sum\limits_{j=1}^{\left\lfloor\frac{b}{d}\right\rfloor} j\sum\limits_{k|\gcd(i,j)}\mu(k)\\
=& d^2 \sum\limits_{k=1}\mu(k)\sum\limits_{i=1}^{\left\lfloor\frac{a}{d}\right\rfloor} i[k|i] \sum\limits_{j=1}^{\left\lfloor\frac{b}{d}\right\rfloor} j[k|j]\\
=& d^2 \sum\limits_{k=1}k^2\mu(k)\sum\limits_{i=1}^{\left\lfloor\frac{a}{kd}\right\rfloor} i\sum\limits_{j=1}^{\left\lfloor\frac{b}{kd}\right\rfloor} j\\
=& d^2\sum\limits_{k=1}k^2\mu(k)\operatorname{sum}{\left(\left\lfloor\frac{a}{kd}\right\rfloor\right)} \operatorname{sum}{\left(\left\lfloor\frac{b}{kd}\right\rfloor\right)}\\
\end{aligned}$$
指数化不动了，代回原式，原式等于：
$$\large \left(\prod_{d=1}d^{\left(d^2\sum\limits_{k=1}k^2\mu(k)\operatorname{sum}{\left(\left\lfloor\frac{a}{kd}\right\rfloor\right)} \operatorname{sum}{\left(\left\lfloor\frac{b}{kd}\right\rfloor\right)}\right)}\right)^{\operatorname{sum}(c)}$$
同 2 面的情况，先展开一下，再枚举 $t=kd$ 和 $d$，原式等于：
$$\large \begin{aligned}
&\left(\prod_{d=1}\left(\prod_{k=1}^{\left\lfloor\frac{n}{d}\right\rfloor}d^{\left(d^2 k^2\mu(k)\right)}\right)^{\left(\operatorname{sum}{\left(\left\lfloor\frac{a}{kd}\right\rfloor\right)} \operatorname{sum}{\left(\left\lfloor\frac{b}{kd}\right\rfloor\right)}\right)}\right)^{\operatorname{sum}(c)}\\
=& \prod_{t=1}\left(\left(\prod_{d|t}d^{\left(d^2\left(\frac{t}{d}\right)^2\mu\left(\frac{t}{d}\right)\right)}\right)^{\operatorname{sum}{\left(\left\lfloor\frac{a}{t}\right\rfloor\right)} \operatorname{sum}{\left(\left\lfloor\frac{b}{t}\right\rfloor\right)}}\right)^{\operatorname{sum}(c)}\\
=& \prod_{t=1}\left(\left(\prod_{d|t}d^{\left(t^2\mu\left(\frac{t}{d}\right)\right)}\right)^{\operatorname{sum}{\left(\left\lfloor\frac{a}{t}\right\rfloor\right)} \operatorname{sum}{\left(\left\lfloor\frac{b}{t}\right\rfloor\right)}}\right)^{\operatorname{sum}(c)}
\end{aligned}$$
与二面相同，设：
$$\large g_1(t) = \prod_{d|t}d^{\left(t^2\mu\left(\frac{t}{d}\right)\right)}$$
$g_1(t)$ 可以用埃氏筛套快速幂筛出，时间复杂度 $O(n\log^2 n)$。再代回原式，原式等于：
$$\prod_{t=1}\left(g_1(t)^{\operatorname{sum}{\left(\left\lfloor\frac{a}{t}\right\rfloor\right)} \operatorname{sum}{\left(\left\lfloor\frac{b}{t}\right\rfloor\right)}}\right)^{\operatorname{sum}(c)}$$
同样预处理 $g_1(t)$ 的前缀积及其逆元，时间复杂度 $O(n\log n)$。
整除分块 + 快速幂即可，单次时间复杂度 $O(\sqrt n\log n)$。
注意指数的取模。
---
### type = 2
$$\begin{aligned}
f_1(a,b,c) &= \prod_{i=1}^{a}\prod_{j=1}^{b}\prod_{k=1}^{c} i^{\gcd(i,j,k)}\\
f_2(a,b,c) &= \prod_{i=1}^{a}\prod_{j=1}^{b}\prod_{k=1}^{c} \gcd(i,j)^{\gcd(i,j,k)}
\end{aligned}$$
考虑 5 面，手段同上，大力反演化简一波，再调换枚举对象，则有：
$$\large \begin{aligned}
&\prod_{i=1}^{a}\prod_{j=1}^{b}\prod_{k=1}^{c} i^{\gcd(i,j,k)}\\
=&\prod_{d=1}\prod\limits_{i=1}^{a}i^{\left(\sum\limits_{j=1}^{b}\sum\limits_{k=1}^{c}[\gcd(i,j,k)=d]\right)}\\
=& \prod_{d=1}\prod\limits_{i=1}^{a}i^{\left(\sum\limits_{j=1}^{\left\lfloor\frac{b}{d}\right\rfloor}\sum\limits_{k=1}^{\left\lfloor\frac{c}{d}\right\rfloor}[\gcd(\frac{i}{d},j,k)=1]\right)}\\
=& \prod_{d=1}\prod\limits_{i=1}^{\left\lfloor\frac{a}{d}\right\rfloor}(id)^{\left(d\sum\limits_{j=1}^{\left\lfloor\frac{b}{d}\right\rfloor}\sum\limits_{k=1}^{\left\lfloor\frac{c}{d}\right\rfloor}[\gcd(i,j,k)=1]\right)}\\
=& \prod_{d=1}\prod\limits_{i=1}^{\left\lfloor\frac{a}{d}\right\rfloor}(id)^{\left(d\sum\limits_{j=1}^{\left\lfloor\frac{b}{d}\right\rfloor}\sum\limits_{k=1}^{\left\lfloor\frac{c}{d}\right\rfloor}\sum\limits_{x|\gcd(i,j,k)}{\mu(x)}\right)}\\
=& \prod_{d=1}\prod\limits_{i=1}^{\left\lfloor\frac{a}{d}\right\rfloor}(id)^{\left(d\sum\limits_{x=1}\mu(x)[x|i]\sum\limits_{j=1}^{\left\lfloor\frac{b}{d}\right\rfloor}[x|j]\sum\limits_{k=1}^{\left\lfloor\frac{c}{d}\right\rfloor}[x|k]\right)}\\
=& \prod_{d=1}\prod_{x=1}\prod\limits_{i=1}^{\left\lfloor\frac{a}{d}\right\rfloor}(id)^{\left(d\times \mu(x)[x|i]\sum\limits_{j=1}^{\left\lfloor\frac{b}{d}\right\rfloor}[x|j]\sum\limits_{k=1}^{\left\lfloor\frac{c}{d}\right\rfloor}[x|k]\right)}\\
=& \prod_{d=1}\prod_{x=1}\prod\limits_{i=1}^{\left\lfloor\frac{a}{xd}\right\rfloor}(ixd)^{\left(d\times \mu(x){\left\lfloor\frac{b}{xd}\right\rfloor}{\left\lfloor\frac{c}{xd}\right\rfloor}\right)}\\
=& \prod_{t = 1}\prod_{d|T}\prod_{i=1}^{\left\lfloor\frac{a}{t}\right\rfloor}(it)^{\left(d\times \mu\left(\frac{t}{d}\right){\left\lfloor\frac{b}{t}\right\rfloor}{\left\lfloor\frac{c}{t}\right\rfloor}\right)}\\
=& \prod_{t = 1}\prod_{d|T}\left(t^{\left\lfloor\frac{a}{t}\right\rfloor}\prod_{i=1}^{\left\lfloor\frac{a}{t}\right\rfloor}i\right)^{d\times \mu\left(\frac{t}{d}\right){\left\lfloor\frac{b}{t}\right\rfloor}{\left\lfloor\frac{c}{t}\right\rfloor}}\\
\end{aligned}$$
引入 $\operatorname{fac}(n) = \prod_{i=1}^{n} i$，再根据枚举对象调整一下指数，原式等于：
$$\large \begin{aligned}
&\prod_{t = 1}\prod_{d|t}\left(t^{\left\lfloor\frac{a}{t}\right\rfloor}\times \operatorname{fac}\left(\left\lfloor\frac{a}{t}\right\rfloor\right)\right)^{\left(d\times \mu\left(\frac{t}{d}\right){\left\lfloor\frac{b}{t}\right\rfloor}{\left\lfloor\frac{c}{t}\right\rfloor}\right)}\\
=& \prod_{t = 1}\left(\prod_{d|t}\left(t^{\left\lfloor\frac{a}{t}\right\rfloor}\times \operatorname{fac}\left(\left\lfloor\frac{a}{t}\right\rfloor\right)\right)^{d\times \mu\left(\frac{t}{d}\right)}\right)^{{\left\lfloor\frac{b}{t}\right\rfloor}{\left\lfloor\frac{c}{t}\right\rfloor}}\\
=& \prod_{t = 1}\left(\left(t^{\left\lfloor\frac{a}{t}\right\rfloor}\times \operatorname{fac}\left(\left\lfloor\frac{a}{t}\right\rfloor\right)\right)^{\sum\limits_{d|t}d\times \mu\left(\frac{t}{d}\right)}\right)^{{\left\lfloor\frac{b}{t}\right\rfloor}{\left\lfloor\frac{c}{t}\right\rfloor}}
\end{aligned}$$
指数中出现了一个经典的狄利克雷卷积的形式，对其进行反演。
将 $(\operatorname{Id}\ast \mu) (n)= \varphi (n)$ 代入原式，原式等于：
$$\large \begin{aligned}
&\prod_{t = 1}\left(t^{\left\lfloor\frac{a}{t}\right\rfloor}\times \operatorname{fac}\left(\left\lfloor\frac{a}{t}\right\rfloor\right)\right)^{\varphi(t){\left\lfloor\frac{b}{t}\right\rfloor}{\left\lfloor\frac{c}{t}\right\rfloor}}\\
=& \prod_{t = 1}\left(t^{\varphi(t)\left\lfloor\frac{a}{t}\right\rfloor{\left\lfloor\frac{b}{t}\right\rfloor}{\left\lfloor\frac{c}{t}\right\rfloor}}\times \operatorname{fac}\left(\left\lfloor\frac{a}{t}\right\rfloor\right)^{\varphi(t){\left\lfloor\frac{b}{t}\right\rfloor}{\left\lfloor\frac{c}{t}\right\rfloor}}\right)
\end{aligned}$$
预处理 $t^{\varphi(t)}$ 的前缀积及逆元，阶乘的前缀积及阶乘逆元，$\pmod {p-1}$ 下的 $\varphi(t)$ 的前缀和（指数
），时间复杂度 $O(n\log n)$。
同样整除分块 + 快速幂即可，单次时间复杂度 $O(\sqrt n\log n)$。
---
然后是最掉 sans 的 6 面。有 $\gcd(i,j,k) = \gcd(\gcd(i,j), k)$，考虑先枚举 $\gcd(i,j)$，然后套路化式子，则有：
$$\large \begin{aligned}
&\prod_{i=1}^{a}\prod_{j=1}^{b}\prod_{k=1}^{c} \gcd(i,j)^{\gcd(i,j,k)}\\
=& \prod_{d=1}\prod_{i=1}^{a}\prod_{j=1}^{b}\prod_{k=1}^{c} [\gcd(i,j)=d] d^{\gcd(d,k)}\\
=& \prod_{d=1} \left(d^{\left(\sum\limits_{i=1}^{a}\sum\limits_{j=1}^{b} [\gcd(i,j)=d]\right)}\right)^{\sum\limits_{k=1}^{c}\gcd(d,k)}
\end{aligned}$$
先考虑最外面的指数，这也是个套路，可以参考 [一个例子](https://www.cnblogs.com/luckyblock/p/12654760.html#%E4%BE%8B-1)。用 $\operatorname{Id} = \varphi \ast 1$ 反演，显然有：
$$\large \begin{aligned}
&\sum\limits_{k=1}^{c}\gcd(d,k)\\
=& \sum\limits_{k=1}^{c}\sum_{x|\gcd(d,k)}\varphi(x)\\
=& \sum_{x=1}\varphi(x)[x|d]\sum_{k=1}^{c}[x|k]\\
=& \sum_{x|d}\varphi(x)\left\lfloor\frac{c}{x}\right\rfloor
\end{aligned}$$
再考虑里面的指数，发现这式子在 2 面已经推了一遍了，于是直接拿过来用，有：
$$\sum\limits_{i=1}^{a}\sum\limits_{j=1}^{b}[\gcd(i,j) = d]=\sum_{y=1}\mu(y)\left\lfloor\dfrac{a}{yd}\right\rfloor\left\lfloor\dfrac{b}{yd}\right\rfloor$$
将化简后的两个指数代入原式，原式等于：
$$\large \begin{aligned}
&\prod_{d=1} \left(d^{\left(\sum\limits_{y=1}\mu(y)\left\lfloor\frac{a}{yd}\right\rfloor\left\lfloor\frac{b}{yd}\right\rfloor\right)}\right)^{\sum\limits_{x|d}\varphi(x)\left\lfloor\frac{c}{x}\right\rfloor}\\
=& \prod_{d=1} \left(\prod\limits_{y=1}d^{\left(\mu(y)\left\lfloor\frac{a}{yd}\right\rfloor\left\lfloor\frac{b}{yd}\right\rfloor\right)}\right)^{\sum\limits_{x|d}\varphi(x)\left\lfloor\frac{c}{x}\right\rfloor}
\end{aligned}$$
与 2、4 面同样套路地，考虑枚举 $t=yd$ 和 $d$，再略作调整，原式等于：
$$\large \begin{aligned}
&\prod_{d=1} \left(\prod\limits_{y=1}d^{\left(\mu(y)\left\lfloor\frac{a}{yd}\right\rfloor\left\lfloor\frac{b}{yd}\right\rfloor\right)}\right)^{\sum\limits_{x|d}\varphi(x)\left\lfloor\frac{c}{x}\right\rfloor}\\
=& \prod_{t=1}\prod_{d|t} d^{\left(\mu\left(\frac{t}{d}\right)\left\lfloor\frac{a}{t}\right\rfloor\left\lfloor\frac{b}{t}\right\rfloor\sum\limits_{x|d}\varphi(x)\left\lfloor\frac{c}{x}\right\rfloor\right)}\\
=& \prod_{t=1}\left(\prod_{d|t} d^{\left(\mu\left(\frac{t}{d}\right)\sum\limits_{x|d}\varphi(x)\left\lfloor\frac{c}{x}\right\rfloor\right)}\right)^{\left\lfloor\frac{a}{t}\right\rfloor\left\lfloor\frac{b}{t}\right\rfloor}\\
=& \prod_{t=1}\left(\prod_{d|t} \prod_{x|d}d^{\left(\mu\left(\frac{t}{d}\right)\varphi(x)\left\lfloor\frac{c}{x}\right\rfloor\right)}\right)^{\left\lfloor\frac{a}{t}\right\rfloor\left\lfloor\frac{b}{t}\right\rfloor}
\end{aligned}$$
发现要同时枚举 $d$ 和 $x$，化不动了。
从题解里学到一个比较神的技巧，考虑把 $d$ 拆成 $x$ 和 $\frac{d}{x}$ 分别计算贡献再相乘，即分别计算下两式：
$$\large \begin{aligned}
&\prod_{t=1}\left(\prod_{d|t} \prod_{x|d}x^{\left(\mu\left(\frac{t}{d}\right)\varphi(x)\left\lfloor\frac{c}{x}\right\rfloor\right)}\right)^{\left\lfloor\frac{a}{t}\right\rfloor\left\lfloor\frac{b}{t}\right\rfloor}\\
&\prod_{t=1}\left(\prod_{d|t} \prod_{x|d}{\left(\frac{d}{x}\right)}^{\left(\mu\left(\frac{t}{d}\right)\varphi(x)\left\lfloor\frac{c}{x}\right\rfloor\right)}\right)^{\left\lfloor\frac{a}{t}\right\rfloor\left\lfloor\frac{b}{t}\right\rfloor}
\end{aligned}$$
---
先考虑 $x$ 的情况，首先把枚举 $x$ 调整到最外层。设 $\operatorname{lim}=\max(a,b,c)$，则原式等于：
$$\large \begin{aligned}
&\prod_{x=1} \prod_{t=1}^{\operatorname{lim}}[x|t]\left(\prod_{d|t} [x|d]{x}^{\left(\mu\left(\frac{t}{d}\right)\varphi(x)\left\lfloor\frac{c}{x}\right\rfloor\right)}\right)^{\left\lfloor\frac{a}{t}\right\rfloor\left\lfloor\frac{b}{t}\right\rfloor}\\
=& \prod_{x=1} \prod_{t=1}^{\left\lfloor\frac{\operatorname{lim}}{x}\right\rfloor}\left(\prod_{d|t} {x}^{\left(\mu\left(\frac{tx}{dx}\right)\varphi(x)\left\lfloor\frac{c}{x}\right\rfloor\right)}\right)^{\left\lfloor\frac{a}{tx}\right\rfloor\left\lfloor\frac{b}{tx}\right\rfloor}\\
=& \prod_{x=1} \prod_{t=1}^{\left\lfloor\frac{\operatorname{lim}}{x}\right\rfloor}\prod_{d|t} {x}^{\left(\varphi(x)\left\lfloor\frac{c}{x}\right\rfloor\left\lfloor\frac{a}{tx}\right\rfloor\left\lfloor\frac{b}{tx}\right\rfloor\mu\left(\frac{t}{d}\right)\right)}
\end{aligned}$$
把 $\prod {t}$ 挪到指数位置，原式等于：
$$\large \begin{aligned}
&\prod_{x=1} {x}^{\left(\sum\limits_{t=1}^{\left\lfloor\frac{\operatorname{lim}}{x}\right\rfloor}\sum\limits_{d|t}\varphi(x)\left\lfloor\frac{c}{x}\right\rfloor\left\lfloor\frac{a}{tx}\right\rfloor\left\lfloor\frac{b}{tx}\right\rfloor\mu\left(\frac{t}{d}\right)\right)}\\
=& \prod_{x=1} {x}^{\left(\varphi(x)\left\lfloor\frac{c}{x}\right\rfloor\sum\limits_{t=1}^{\left\lfloor\frac{\operatorname{lim}}{x}\right\rfloor}\left\lfloor\frac{a}{tx}\right\rfloor\left\lfloor\frac{b}{tx}\right\rfloor\sum\limits_{d|t}\mu\left(\frac{t}{d}\right)\right)}
\end{aligned}$$
指数中又出现了一个经典的狄利克雷卷积的形式，对其进行反演。
将 $(\mu \ast 1) (n)= \epsilon (n)=[n=1]$ 代入原式，原式等于：
$$\large \begin{aligned}
&\prod_{x=1} {x}^{\left(\varphi(x)\left\lfloor\frac{c}{x}\right\rfloor\sum\limits_{t=1}^{\left\lfloor\frac{\operatorname{lim}}{x}\right\rfloor}\left\lfloor\frac{a}{tx}\right\rfloor\left\lfloor\frac{b}{tx}\right\rfloor[t=1]\right)}\\
=& \prod_{x=1} {x}^{\left(\varphi(x)\left\lfloor\frac{a}{x}\right\rfloor\left\lfloor\frac{b}{x}\right\rfloor\left\lfloor\frac{c}{x}\right\rfloor\right)}
\end{aligned}$$
得到了一个非常优美的式子，而且发现这个式子是 5 面最终答案的一部分。同 5 面的做法，直接整除分块即可。
---
再考虑 $\frac{d}{x}$ 的情况，同上先把枚举 $x$ 放到最外层，并调整一下指数，则原式等于：
$$\large \begin{aligned}
&\prod_{x=1} \prod_{t=1}^{\operatorname{lim}}[x|t]\left(\prod_{d|t} [x|d]{\left(\frac{d}{x}\right)}^{\left(\mu\left(\frac{t}{d}\right)\varphi(x)\left\lfloor\frac{c}{x}\right\rfloor\right)}\right)^{\left\lfloor\frac{a}{t}\right\rfloor\left\lfloor\frac{b}{t}\right\rfloor}\\
=& \prod_{x=1} \prod_{t=1}^{\left\lfloor\frac{\operatorname{lim}}{x}\right\rfloor}\left(\prod_{d|tx} [x|d]{\left(\frac{d}{x}\right)}^{\left(\mu\left(\frac{tx}{d}\right)\varphi(x)\left\lfloor\frac{c}{x}\right\rfloor\right)}\right)^{\left\lfloor\frac{a}{tx}\right\rfloor\left\lfloor\frac{b}{tx}\right\rfloor}\\
=& \prod_{x=1} \left(\prod_{t=1}^{\left\lfloor\frac{\operatorname{lim}}{x}\right\rfloor}\left(\prod_{d|tx} [x|d]{\left(\frac{d}{x}\right)}^{\mu\left(\frac{tx}{d}\right)}\right)^{\left\lfloor\frac{a}{tx}\right\rfloor\left\lfloor\frac{b}{tx}\right\rfloor}\right)^{\varphi(x)\left\lfloor\frac{c}{x}\right\rfloor}
\end{aligned}$$
考虑枚举 $dx$，替换原来的 $d$，注意一下这里的倍数关系。原式等于：
$$\large \prod_{x=1} \left(\prod_{t=1}^{\left\lfloor\frac{\operatorname{lim}}{x}\right\rfloor}\left(\prod_{d|t}d^{\mu\left(\frac{t}{d}\right)}\right)^{\left\lfloor\frac{a}{tx}\right\rfloor\left\lfloor\frac{b}{tx}\right\rfloor}\right)^{\varphi(x)\left\lfloor\frac{c}{x}\right\rfloor}$$
发现最内层的式子 $\prod_{d|t}d^{\mu\left(\frac{t}{d}\right)}$，即为二面处理过的 $g_0(t)$。直接代入，原式等于：
$$\large \prod_{x=1} \left(\prod_{t=1}^{\left\lfloor\frac{\operatorname{lim}}{x}\right\rfloor}g_0(t)^{\left\lfloor\frac{a}{tx}\right\rfloor\left\lfloor\frac{b}{tx}\right\rfloor}\right)^{\varphi(x)\left\lfloor\frac{c}{x}\right\rfloor}$$
一个小结论，证明可以看 [这里](https://www.cnblogs.com/luckyblock/p/12654760.html#%E5%BC%95%E7%90%861)：
$$\forall a,b,c\in \mathbb{Z},\left\lfloor\dfrac{a}{bc}\right\rfloor = \left\lfloor{\dfrac{\left\lfloor\dfrac{a}{b}\right\rfloor}{c}}\right\rfloor$$
则原式等于：
$$\large \prod_{x=1} \left(\prod_{t=1}^{\left\lfloor\frac{\operatorname{lim}}{x}\right\rfloor}g_0(t)^{\left\lfloor\frac{\left\lfloor\frac{a}{x}\right\rfloor}{t}\right\rfloor\left\lfloor\frac{\left\lfloor\frac{b}{x}\right\rfloor}{t}\right\rfloor}\right)^{\varphi(x)\left\lfloor\frac{c}{x}\right\rfloor}$$
于是可以先对外层整除分块，再对内层整除分块。
然后就做完了，哈哈哈。
## 实现
一些实现上的小技巧：
- 逆元能预处理就预处理。
- 注意对指数取模，模数为 $p-1$。
```cpp
//知识点：莫比乌斯反演
/*
By:Luckyblock
用了比较清晰易懂的变量名，阅读体验应该会比较好。
vsc 的自动补全真是太好啦！
*/
#include <algorithm>
#include <cctype>
#include <cstdio>
#include <cstring>
using std::min;
using std::max;
#define LL long long
const int Lim = 1e5;
const int kN = 1e5 + 10;
//=============================================================
LL A, B, C, mod, ans;
int T, p_num, p[kN];
bool vis[kN];
LL mu[kN], phi[kN], fac[kN], g[2][kN];
LL sumphi[kN], prodt_phi[kN], prodi_i[kN], prodg[2][kN];
LL inv[kN], inv_fac[kN], inv_prodt_phi[kN], inv_prodg[2][kN];
//=============================================================
inline int read() {
int f = 1, w = 0;
char ch = getchar();
for (; !isdigit(ch); ch = getchar())
if (ch == '-') f = -1;
for (; isdigit(ch); ch = getchar()) {
w = (w << 3) + (w << 1) + (ch ^ '0');
}
return f * w;
}
void Chkmax(int &fir_, int sec_) {
if (sec_ > fir_) fir_ = sec_;
}
void Chkmin(int &fir_, int sec_) {
if (sec_ < fir_) fir_ = sec_;
}
LL QPow(LL x_, LL y_) {
x_ %= mod;
y_ %= mod - 1;
LL ret = 1;
for (; y_; y_ >>= 1ll) {
if (y_ & 1) ret = ret * x_ % mod;
x_ = x_ * x_ % mod;
}
return ret;
}
LL Inv(LL x_) {
return QPow(x_, mod - 2);
}
LL Sum(LL n_) {
return ((n_ * (n_ + 1ll)) / 2ll) % (mod - 1);
}
void Euler() {
vis[1] = true, mu[1] = phi[1] = 1; //初值
for (int i = 2; i <= Lim; ++ i) {
if (! vis[i]) {
p[++ p_num] = i;
mu[i] = -1;
phi[i] = i - 1;
}
for (int j = 1; j <= p_num && i * p[j] <= Lim; ++ j) {
vis[i * p[j]] = true;
if (i % p[j] == 0) {
mu[i * p[j]] = 0;
phi[i * p[j]] = phi[i] * p[j];
break;
}
mu[i * p[j]] = -mu[i];
phi[i * p[j]] = phi[i] * (p[j] - 1);
}
}
}
void Prepare() {
Euler();
inv[1] = fac[0] = prodt_phi[0] = prodi_i[0] = 1;
for (int i = 1; i <= Lim; ++ i) {
g[0][i] = g[1][i] = 1;
fac[i] = 1ll * fac[i - 1] * i % mod;
sumphi[i] = (sumphi[i - 1] + phi[i]) % (mod - 1);
prodi_i[i] = prodi_i[i - 1] * QPow(i, i) % mod;
if (i > 1) inv[i] = (mod - mod / i) * inv[mod % i] % mod;
prodt_phi[i] = prodt_phi[i - 1] * QPow(i, phi[i]) % mod;
inv_prodt_phi[i] = Inv(prodt_phi[i]);
}
for (int d = 1; d <= Lim; ++ d) {
for (int j = 1; d * j <= Lim; ++ j) {
int t = d * j;
if (mu[j] == 1) {
g[0][t] = g[0][t] * d % mod;
g[1][t] = g[1][t] * QPow(1ll * d, 1ll * t * t) % mod;
} else if (mu[j] == -1) {
g[0][t] = g[0][t] * inv[d] % mod;
g[1][t] = g[1][t] * Inv(QPow(1ll * d, 1ll * t * t)) % mod;
}
}
}
inv_prodg[0][0] = prodg[0][0] = 1;
inv_prodg[1][0] = prodg[1][0] = 1;
inv_prodt_phi[0] = 1;
for (int i = 1; i <= Lim; ++ i) {
for (int j = 0; j <= 1; ++ j) {
prodg[j][i] = prodg[j][i - 1] * g[j][i] % mod;
inv_prodg[j][i] = Inv(prodg[j][i]);
}
}
}
LL f1(LL a_, LL b_, LL c_, int type) {
if (! type) return QPow(fac[a_], b_ * c_);
if (type == 1) return QPow(prodi_i[a_], Sum(b_) * Sum(c_));
LL ret = 1, lim = min(min(a_, b_), c_);
for (LL l = 1, r = 1; l <= lim; l = r + 1) {
r = min(min(a_ / (a_ / l), b_ / (b_ / l)), c_ / (c_ / l));
ret = ret * QPow(prodt_phi[r] * inv_prodt_phi[l - 1], (a_ / l) * (b_ / l) % (mod - 1) * (c_ / l)) % mod;
ret = ret * QPow(fac[a_ / l], (sumphi[r] - sumphi[l - 1] + mod - 1) % (mod - 1) * (b_ / l) % (mod - 1) * (c_ / l)) % mod;
}
return ret;
}
LL f2_2(LL a_, LL b_) {
LL ret = 1;
for (LL l = 1, r = 1; l <= min(a_, b_); l = r + 1) {
r = min(a_ / (a_ / l), b_ / (b_ / l));
ret = ret * QPow(prodg[0][r] * inv_prodg[0][l - 1], 1ll * (a_ / l) * (b_ / l)) % mod;
}
return ret;
}
LL f2(LL a_, LL b_, LL c_, int type) {
LL ret = 1;
if (! type) {
for (LL l = 1, r = 1; l <= min(a_, b_); l = r + 1) {
r = min(a_ / (a_ / l), b_ / (b_ / l));
LL val = QPow(prodg[0][r] * inv_prodg[0][l - 1], 1ll * (a_ / l) * (b_ / l));
ret = (ret * QPow(val, c_)) % mod;
}
} else if (type == 1) {
for (LL l = 1, r = 1; l <= min(a_, b_); l = r + 1) {
r = min(a_ / (a_ / l), b_ / (b_ / l));
LL val = QPow(prodg[1][r] * inv_prodg[1][l - 1], Sum(a_ / l) * Sum(b_ / l));
ret = (ret * QPow(val, Sum(c_))) % mod;
}
} else {
LL lim = min(min(a_, b_), c_);
for (LL l = 1, r = 1; l <= lim; l = r + 1) {
r = min(min(a_ / (a_ / l), b_ / (b_ / l)), c_ / (c_ / l));
ret = ret * QPow(f2_2(a_ / l, b_ / l), (sumphi[r] - sumphi[l - 1] + mod - 1) % (mod - 1) * (c_ / l)) % mod;
ret = ret * QPow(prodt_phi[r] * inv_prodt_phi[l - 1], (a_ / l) * (b_ / l) % (mod - 1) * (c_ / l)) % mod;
}
}
return ret;
}
//=============================================================
int main() {
T = read(), mod = read();
Prepare();
while (T -- ) {
A = read(), B = read(), C = read();
for (int i = 0; i <= 2; ++ i) {
ans = f1(A, B, C, i) * f1(B, A, C, i) % mod;
ans = ans * Inv(f2(A, B, C, i)) % mod * Inv(f2(A, C, B, i)) % mod;
printf("%lld ", ans);
}
printf("\n");
}
return 0;
}
```