幽灵乐团

写一下幽灵乐团的式子推导过程

题目及式子

求解 \[\prod_{i=1}^A\prod_{j=1}^B\prod_{k=1}^C \frac{\operatorname{lcm}(i,j)}{\gcd(i,k)}^{f(type)} \bmod P, type = 0,1,2\] 其中 \(f(0) = 1, f(1) = ijk,f(2) = \gcd(i,j,k)\) \(1 \leq A,B,C \leq 10^5, P\in \{prime\}, 10^7 \leq P \leq 1.05 \times 10^9\) 后面推导式子过程中会使用一些中间公式进行替换，并且省略求和/求积符号下的"=1"

基本变换

\[\begin{align*} &\prod_i^A\prod_j^B\prod_k^C \frac{\operatorname{lcm}(i,j)}{\gcd(i,k)}^{f(type)}\\ &=\prod_i^A\prod_j^B\prod_k^C \frac{ij}{\gcd(i,j)\gcd(i,k)}^{f(type)}\\ &=\frac { \prod_i^A\prod_j^B\prod_k^C i^{f(type)}\times \prod_i^A\prod_j^B\prod_k^C j^{f(type)} } { \prod_i^A\prod_j^B\prod_k^C gcd(i,j)^{f(type)} \times \prod_i^A\prod_j^B\prod_k^C gcd(i,k)^{f(type)} }\\ &=\frac { F_1(A,B,C) \times F_1(B,A,C) } { F_2(A,B,C) \times F_2(A,C,B) } \end{align*}\]

其中： \[F_1(A,B,C) = \prod_i^A\prod_j^B\prod_k^C i^{f(type)}\] \[F_2(A,B,C) = \prod_i^A\prod_j^B\prod_k^C gcd(i,j)^{f(type)}\] 于是我们可以把原式拆开成两个独立的部分\(F_1,F_2\)计算。 下面来依次推理\(type = 0,1,2\)时的式子。 用\(N\) 表示\(A,B,C\)的\(\min\)，可能是一部分。

\(type = 0\)

最简单的

\[\begin{align*} F_1(A,B,C) &=\prod_i^A\prod_j^B\prod_k^C i\\ &= {i!}^{BC} \end{align*}\]

\[\begin{align*} F_2(A,B,C) &= \prod_i^A\prod_j^B\prod_k^C \gcd(i,j) \\ &= \prod_i^A\prod_j^B \gcd(i,j)^{C} \\ &= \prod_d^N d^{\sum_i^A \sum_j^B [\gcd(i,j) = d] \times C} &\text{(枚举gcd)}\\ &= \prod_d^N d^{\sum\limits_x^{\lfloor\frac{N}{d}\rfloor} \mu(x) \lfloor\frac{A}{dx}\rfloor \lfloor\frac{B}{dx}\rfloor \times C} &\text{(莫反)}\\ &= \prod_T^N (\prod_{d | T} d^{\mu(\frac{T}{d})})^{ \lfloor\frac{A}{dx}\rfloor \lfloor\frac{B}{dx}\rfloor \times C} &\text{(枚举 $T = dx$)}\\ &= \prod_T^N M_0(T)^{ \lfloor\frac{A}{dx}\rfloor \lfloor\frac{B}{dx}\rfloor \times C} \end{align*}\]

其中\(M_0\)可以预处理，一种方法是\(O(n\log n)\)枚举因子计算贡献，还有一种是\(O(n \log\log n)\)类似狄利克雷前缀和去做，不过理解起来有些困难。 处理出\(M_0\)后，每次询问直接整除分块即可，单次时间复杂度\(O(\sqrt n \log n)\)

\(type = 1\)

令 \(S_1(x) = \frac{x(x + 1)}{2}\)

\[\begin{align*} F_1(A,B,C) &=\prod_i^A\prod_j^B\prod_k^C i^{ijk}\\ &= (\prod_i i^i)^{\sum_1^B j \times \sum_1^C k}\\ &= (\prod_i i^i)^{S_1(B) S_1(C)} \end{align*}\]

预处理\(i^i\)前缀积即可\(O(\log n)\)计算

\[\begin{align*} F_2(A,B,C) &= \prod_i^A\prod_j^B\prod_k^C\gcd(i,j)^{ijk}\\ &= (\prod_i^A\prod_j^B \gcd(i,j)^{ij})^{S_1(C)} \end{align*}\]

把里面的式子拿出来：

\[\begin{align*} & \prod_i^A\prod_j^B \gcd(i,j)^{ij}\\ &= \prod_d^N d ^{\sum_i^A \sum_j^B [gcd(i,j)=d] \times ij}\\ &= \prod_d^N d^{d^2 \sum\limits_i^{\lfloor\frac{A}{d}\rfloor} \sum\limits_j^{\lfloor\frac{B}{d}\rfloor} [gcd(i,j) = 1] \times (ij) } \text{(把因子$d$提出来)}\\ &= \prod_d^N d^{d^2 \sum\limits_i^{\lfloor\frac{A}{d}\rfloor} \sum\limits_j^{\lfloor\frac{B}{d}\rfloor} (ij) \sum\limits_{x|i,x|j} \mu(x) }\text{(莫反)}\\ &= \prod_d^N d^{d^2 \sum\limits_x^{\lfloor\frac{N}{d}\rfloor} \mu(x) \sum\limits_{x | i} i \sum\limits_{x | j} j }\text{(把$x$提到前面，后面准备变形)}\\ &= \prod_d^N d^{d^2 \sum\limits_x^{\lfloor\frac{N}{d}\rfloor} \mu(x) xS_1(\lfloor\frac{A}{dx}\rfloor) xS_1(\lfloor\frac{B}{dx}\rfloor) } \text{(计算求和式，提出因子)}\\ &= \prod_d^N d^{ \sum\limits_x^{\lfloor\frac{N}{d}\rfloor}(dx)^2 \mu(x) \times S_1(\lfloor\frac{A}{dx}\rfloor) S_1(\lfloor\frac{B}{dx}\rfloor) }\text{(整理一下)}\\ &= \prod_T^N \left((\prod_{d|T} d^{\mu(\frac{T}{d})})^{T^2} \right) ^ {S_1(\lfloor\frac{A}{T}\rfloor) S_1(\lfloor\frac{B}{T}\rfloor)} \text{(枚举$T = dx$)}\\ &= \prod_T^N \left(M_2(T) \right) ^ {S_1(\lfloor\frac{A}{T}\rfloor) S_1(\lfloor\frac{B}{T}\rfloor)} \end{align*}\]

\(M_2(T) = M_0(T) ^{T^2}\),在前面\(M_0\)的基础上预处理\(M_2\),同样整除分块计算即可做到\(O(\sqrt n \log n)\)的单次复杂度。

\(type = 2\)

这部分是看题解才会的

\[\begin{align*} &F_1(A,B,C) \\ &= \prod_i^A\prod_j^B\prod_k^C i^{\gcd(i,j,k)}\\ &= \prod_i^A i ^{\sum_j^B \sum_k^C \gcd(i,j,k)} \\ &= \prod_i^A i ^{\sum_j^B \sum_k^C \sum_{\gcd(j,k)|i}\gcd(j,k) } \text{(换种写法，把$i$分出来方便枚举gcd)}\\ &= \prod_i^A i ^{\sum_j^B \sum_k^C (\sum\limits_{x|i,x | j,x|k} \phi(x))} \text{(经典转化$\mathrm{id} = \phi * I$)}\\ &= \prod_i^A i ^{\sum\limits_{x | i}\phi(x) \lfloor\frac{B}{x}\rfloor \lfloor\frac{C}{x}\rfloor} \text{(改为枚举gcd = $x$)}\\ &=\prod_x^N (\prod_{x|i} i) ^{\phi(x)\lfloor\frac{B}{x}\rfloor \lfloor\frac{C}{x}\rfloor} \text{(把$x$放在外面)}\\ &=\prod_x^N (x^{\lfloor\frac{A}{x}\rfloor} (\lfloor\frac{A}{x}\rfloor!)) ^{\phi(x)\lfloor\frac{B}{x}\rfloor \lfloor\frac{C}{x}\rfloor} \text{(计算里面的乘积)}\\ &= \prod_x^N (x ^{\phi(x)}) ^{ \lfloor\frac{A}{x}\rfloor \lfloor\frac{B}{x}\rfloor \lfloor\frac{C}{x}\rfloor } \times \prod_x^N (\lfloor\frac{A}{x}\rfloor!) ^{\phi(x)\lfloor\frac{B}{x}\rfloor \lfloor\frac{C}{x}\rfloor} \end{align*}\]

预处理\(x^{\phi(x)}\)的前缀积和\(\phi(x)\)的前缀和(注意对\(\phi(P) = P - 1\)取模)即可通过整除分块计算。时间复杂度\(O(\sqrt n\log n)\)

最折磨的还是下面这个式子

\[\begin{align*} &F_2(A,B,C)\\ &= \prod_i^A\prod_j^B\prod_k^C \gcd(i,j)^{\gcd(i,j,k)}\\ &= \prod_d^N d^{\sum_i^A\sum_j^B [\gcd(i,j) = d] \times \sum_k^C \gcd(d,k) }\text{(枚举gcd)}\\ &= \prod_d^N d^{\sum\limits_x^{\lfloor\frac{N}{d} \rfloor} \mu(x) \lfloor\frac{A}{dx}\rfloor \lfloor\frac{B}{dx}\rfloor \times \sum\limits_{e|d} \phi(e) \lfloor\frac{C}{e}\rfloor} \text{(对两部分莫反)}\\ &= \prod_d^N d^{\sum\limits_x^{\lfloor\frac{N}{d} \rfloor} \mu(x) \lfloor\frac{A}{dx}\rfloor \lfloor\frac{B}{dx}\rfloor G(C,d)} \text{(简记)}\\ &= \prod_T^N (\prod_{d | T} d ^ {\mu(\frac{T}{d}) \times \sum\limits_{x|d} \phi(x) \lfloor\frac{C}{x}\rfloor}) ^{\lfloor\frac{A}{T}\rfloor \lfloor\frac{B}{T}\rfloor} \text{(这里$x$已经不一样了)} \end{align*}\]\

上面我们的步骤都是枚举\(T = dx\),把 \(T\) 相关部分放到最外面，预处理内部依赖于\(T\)的部分求解，但是\(G(C,d)\)还依赖于\(C\),这使得我们无法对不同的\(C\)预处理，必须想办法寻求别的方法求解。 通过学习题解，这里又一个阴间小技巧，就是把\(d\)拆成\(d = x\cdot \frac{d}{x}\),再继续化简成可以预处理方便求解的形式。

\(x\)部分

\[\begin{align*} & \prod_T^N (\prod_{d | T} x ^ {\mu(\frac{T}{d}) \times \sum\limits_{x|d} \phi(x) \lfloor\frac{C}{x}\rfloor}) ^{\lfloor\frac{A}{T}\rfloor \lfloor\frac{B}{T}\rfloor} \\ &=\prod_T^N (\prod_{d | T} \prod_{x | d} x ^ {\mu(\frac{T}{d}) \phi(x) \lfloor\frac{C}{x}\rfloor}) ^{\lfloor\frac{A}{T}\rfloor \lfloor\frac{B}{T}\rfloor} \\ &=\prod_x^N \prod_T^{\lfloor\frac{N}{x}\rfloor} (\prod_{d|T} x ^{\mu(\frac{T}{d})\phi(x)\lfloor\frac{C}{x}\rfloor}) ^{\lfloor\frac{A}{xT}\rfloor \lfloor\frac{B}{xT}\rfloor}\text{(把$x$放到前面)}\\ &=\prod_x^N \prod_T^{\lfloor\frac{N}{x}\rfloor} \prod_{d|T} x ^{\mu(\frac{T}{d})\phi(x)\lfloor\frac{A}{xT}\rfloor \lfloor\frac{B}{xT}\rfloor\lfloor\frac{C}{x}\rfloor}\\ &=\prod_x^N \prod_T^{\lfloor\frac{N}{x}\rfloor} x ^{(\sum\limits_{d|T}\mu(\frac{T}{d}))\phi(x)\lfloor\frac{A}{xT}\rfloor \lfloor\frac{B}{xT}\rfloor\lfloor\frac{C}{x}\rfloor}\text{(莫反魔术的前奏)}\\ &=\prod_x^N \prod_T^{\lfloor\frac{N}{x}\rfloor} x ^{[T = 1]\phi(x)\lfloor\frac{A}{xT}\rfloor \lfloor\frac{B}{xT}\rfloor\lfloor\frac{C}{x}\rfloor} \text{($\mu * 1 = \epsilon$)}\\ &=\prod_x^N x ^{\phi(x)\lfloor\frac{A}{x}\rfloor \lfloor\frac{B}{x}\rfloor\lfloor\frac{C}{x}\rfloor} \\ \end{align*}\]\

这部分我们在前面已经求过

\(\frac{d}{x}\)部分

\[\begin{align*} &\prod_T^N (\prod_{d | T} (\frac{d}{x}) ^ {\mu(\frac{T}{d}) \times \sum\limits_{x|d} \phi(x) \lfloor\frac{C}{x}\rfloor}) ^{\lfloor\frac{A}{T}\rfloor \lfloor\frac{B}{T}\rfloor} \\ &=\prod_x^N \prod_T^{\lfloor\frac{N}{x}\rfloor} (\prod_{d|xT,x|d} (\frac{d}{x}) ^{\mu(\frac{xT}{d})\phi(x)\lfloor\frac{C}{x}\rfloor}) ^{\lfloor\frac{A}{xT}\rfloor \lfloor\frac{B}{xT}\rfloor}\text{(原来的$T$被换成$\frac{T}{x}$)}\\ &=\prod_x^N \prod_T^{\lfloor\frac{N}{x}\rfloor} (\prod_{d|xT} (\frac{d}{x}) ^{\mu(\frac{xT}{d})}) ^{\lfloor\frac{A}{xT}\rfloor \lfloor\frac{B}{xT}\rfloor \phi(x)\lfloor\frac{C}{x}\rfloor} \\ &= \prod_x^N \prod_T^{\lfloor\frac{N}{x}\rfloor} (\prod_{e|T} e ^{\mu(\frac{T}{e})}) ^{\lfloor\frac{A}{xT}\rfloor \lfloor\frac{B}{xT}\rfloor \phi(x)\lfloor\frac{C}{x}\rfloor} \text{(替换$e = \frac{d}{x}$)}\\ &= \prod_x^N \left(\prod_T^{\lfloor\frac{N}{x}\rfloor} (M_0(T)) ^{\lfloor\frac{\lfloor\frac{A}{x}\rfloor}{T}\rfloor \lfloor\frac{\lfloor\frac{B}{x}\rfloor}{T}\rfloor} \right)^{\phi(x)\lfloor\frac{C}{x}\rfloor} \text{(分一下块)}\\ \end{align*}\]

通过变换，我们得到了一个两层分块的结构。预处理\(M_0\)和\(\phi(x)\)的前缀和后，单次求解时间复杂度是\(O(n^{0.75}\log n)\)，不过也可以通过预处理合适值域内部式子的值，做到\(O(n^{\frac{2}{3}}\log n)\).

这样我们就把这题给做完了。 需要注意的一些点： 1. \(\phi\)前缀和和指数上的计算取模\(\phi(P)-1\). 2. 预处理\(M_0\),\(\phi\)的前缀积等函数的逆元，否则常数会变得较大，不好通过该题。