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

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

题目简述

求：

\[\prod_{i=1}^A\prod_{j=1}^B\prod_{k=1}^C\left(\frac{lcm(i,j)}{\gcd(i,k)}\right)^{f(type)} \]

对于

\[f(0)=1 \\ f(1)=i\cdot j\cdot k \\ f(2)=\gcd(i,j,k) \]

分别求解. 答案对一个给出的质数 \(P\) 取模.

令 \(N\) 为 \(A,B,C\) 的范围，\(N=10^5\).

\(10^7\leq P\leq 1.05\times 10^9\).

数据组数 \(T=70\).

推导过程

通用部分

因为答案对质数 \(P\) 取模，所以在除法时可以使用逆元，于是拆分分子分母是可行的.

\[\begin{align*} &\prod_{i=1}^A\prod_{j=1}^B\prod_{k=1}^C\left(\frac{lcm(i,j)}{\gcd(i,k)}\right)^{f(type)} \\ =&\prod_{i=1}^A\prod_{j=1}^B\prod_{k=1}^C\frac{lcm(i,j)^{f(type)}}{\gcd(i,k)^{f(type)}} \\ =&\frac{\prod_{i=1}^A\prod_{j=1}^B\prod_{k=1}^Clcm(i,j)^{f(type)}}{\prod_{i=1}^A\prod_{j=1}^B\prod_{k=1}^C\gcd(i,k)^{f(type)}} \\ =&\frac{\prod_{k=1}^C\left(\prod_{i=1}^A\prod_{j=1}^Blcm(i,j)^{f(type)}\right)}{\prod_{j=1}^B\left(\prod_{i=1}^A\prod_{k=1}^C\gcd(i,k)^{f(type)}\right)} \\ =&\frac{\prod_{i=1}^A\prod_{j=1}^Blcm(i,j)^{\sum_{k=1}^Cf(type)}}{\prod_{i=1}^A\prod_{k=1}^C\gcd(i,k)^{\sum_{j=1}^Bf(type)}} \end{align*} \]

其中，

\[\begin{align*} &\prod_{i=1}^A\prod_{j=1}^Blcm(i,j)^{\sum_{k=1}^Cf(type)} \\ =&\prod_{i=1}^A\prod_{j=1}^B\left(\frac{i\cdot j}{\gcd(i,j)}\right)^{\sum_{k=1}^Cf(type)} \\ =&\frac{\prod_{i=1}^A\prod_{j=1}^Bi^{\sum_{k=1}^Cf(type)}\cdot\prod_{i=1}^A\prod_{j=1}^Bj^{\sum_{k=1}^Cf(type)}}{\prod_{i=1}^A\prod_{j=1}^B\gcd(i,j)^{\sum_{k=1}^Cf(type)}} \\ =&\frac{\prod_{i=1}^Ai^{\sum_{j=1}^B\sum_{k=1}^Cf(type)}\cdot\prod_{j=1}^Bj^{\sum_{i=1}^A\sum_{k=1}^Cf(type)}}{\prod_{i=1}^A\prod_{j=1}^B\gcd(i,j)^{\sum_{k=1}^Cf(type)}} \end{align*} \]

可以发现

\[\prod_{i=1}^A\prod_{j=1}^B\gcd(i,j)^{\sum_{k=1}^Cf(type)} \quad \text{和} \quad \prod_{i=1}^A\prod_{k=1}^C\gcd(i,k)^{\sum_{j=1}^Bf(type)} \quad \text{结构相同} \]

\[\prod_{i=1}^Ai^{\sum_{j=1}^B\sum_{k=1}^Cf(type)} \quad \text{和} \quad \prod_{j=1}^Bj^{\sum_{i=1}^A\sum_{k=1}^Cf(type)} \quad \text{结构相同} \]

因此，设

\[F_{type}(A,B,C)=\prod_{i=1}^A\prod_{j=1}^B\gcd(i,j)^{\sum_{k=1}^Cf(type)} \]

\[G_{type}(A,B,C)=\prod_{i=1}^Ai^{\sum_{j=1}^B\sum_{k=1}^Cf(type)} \]

则

\[\prod_{i=1}^A\prod_{k=1}^C\gcd(i,k)^{\sum_{j=1}^Bf(type)}=F_{type}(A,C,B) \]

\[\prod_{j=1}^Bj^{\sum_{i=1}^A\sum_{k=1}^Cf(type)}=G_{type}(B,A,C) \]

最终

\[\begin{align*} &\prod_{i=1}^A\prod_{j=1}^B\prod_{k=1}^C\left(\frac{lcm(i,j)}{\gcd(i,k)}\right)^{f(type)} \\ =&\frac{G_{type}(A,B,C)\cdot G_{type}(B,A,C)/F_{type}(A,B,C)}{F_{type}(A,C,B)} \\ =&\frac{G_{type}(A,B,C)\cdot G_{type}(B,A,C)}{F_{type}(A,B,C)\cdot F_{type}(A,C,B)} \end{align*} \]

因此下文的讨论只涉及 \(F\) 和 \(G\).

type=0

\(G_0(A,B,C)\)

\[\begin{align*} G_0(A,B,C)&=\prod_{i=1}^Ai^{\sum_{j=1}^B\sum_{k=1}^Cf(type)} \\ &=\prod_{i=1}^Ai^{\sum_{j=1}^B\sum_{k=1}^C1} \\ &=\prod_{i=1}^Ai^{BC} \\ &=\left(\prod_{i=1}^Ai\right)^{BC} \end{align*} \]

预处理时间复杂度：预处理 \(\prod_{i=1}^xi\)，\(O(N)\).

单次查询时间复杂度：一次快速幂，\(O(\log N)\).

\(F_0(A,B,C)\)

\[\begin{align*} F_0(A,B,C)&=\prod_{i=1}^A\prod_{j=1}^B\gcd(i,j)^{\sum_{k=1}^Cf(type)} \\ &=\prod_{i=1}^A\prod_{j=1}^B\gcd(i,j)^C \\ &=\left(\prod_{i=1}^A\prod_{j=1}^B\gcd(i,j)\right)^C \\ &=\left(\prod_{d=1}^{\min(A,B)}\prod_{\substack{1\leq i\leq A\\[2pt]1\leq j\leq B\\[2pt]\gcd(i,j)=d}}d\right)^C \\ &=\left(\prod_{d=1}^{\min(A,B)}\prod_{\substack{1\leq i\leq\lfloor A/d\rfloor\\[2pt]1\leq j\leq\lfloor B/d\rfloor\\[2pt]\gcd(i,j)=1}}d\right)^C \\ &=\left(\prod_{d=1}^{\min(A,B)}d^{\sum_{i=1}^{\lfloor A/d\rfloor}\sum_{j=1}^{\lfloor B/d\rfloor}[\gcd(i,j)=1]}\right)^C \end{align*} \]

其中，

\[\begin{align*} &\sum_{i=1}^{\lfloor A/d\rfloor}\sum_{j=1}^{\lfloor B/d\rfloor}\bigl[\gcd(i,j)=1\bigr] \\ =&\sum_{i=1}^{\lfloor A/d\rfloor}\sum_{j=1}^{\lfloor B/d\rfloor}\sum_{x|i,\,x|j}\mu(x) \\ =&\sum_{x=1}^{\min(\lfloor A/d\rfloor,\lfloor B/d\rfloor)}\mu(x)\cdot\sum_{i=1}^{\lfloor\frac{A}{dx}\rfloor}\sum_{j=1}^{\lfloor \frac{B}{dx}\rfloor}1 \\ =&\sum_{x=1}^{\min(\lfloor A/d\rfloor,\lfloor B/d\rfloor)}\mu(x)\cdot\left\lfloor\frac{A}{dx}\right\rfloor\cdot\left\lfloor\frac{B}{dx}\right\rfloor \end{align*} \]

于是

\[\begin{align*} F_0(A,B,C)=&\left(\prod_{d=1}^{\min(A,B)}d^{\sum_{i=1}^{\lfloor A/d\rfloor}\sum_{j=1}^{\lfloor B/d\rfloor}[\gcd(i,j)=1]}\right)^C \\ =&\left(\prod_{d=1}^{\min(A,B)}d^{\sum_{x=1}^{\min(\lfloor A/d\rfloor,\lfloor B/d\rfloor)}\mu(x)\cdot\left\lfloor\frac{A}{dx}\right\rfloor\cdot\left\lfloor\frac{B}{dx}\right\rfloor}\right)^C \\ =&\left(\prod_{d=1}^{\min(A,B)}d^{\sum_{x=1}^{\lfloor\min(A,B)/d\rfloor}\mu(x)\cdot\left\lfloor\frac{A}{dx}\right\rfloor\cdot\left\lfloor\frac{B}{dx}\right\rfloor}\right)^C \\ =&\left(\prod_{T=1}^{\min(A,B)}\prod_{d|T}d^{\mu(T/d)\cdot\lfloor A/T\rfloor\cdot\lfloor B/T\rfloor}\right)^C \\ =&\left(\prod_{T=1}^{\min(A,B)}\left(\prod_{d|T}d^{\mu(T/d)}\right)^{\lfloor A/T\rfloor\cdot\lfloor B/T\rfloor}\right)^C \end{align*} \]

令

\[f(T)=\prod_{d|T}d^{\mu(T/d)} \]

接下来考虑 \(f\) 的性质：

设

\[T=p_1^{e_1}p_2^{e_2}\dots p_m^{e_m} \]

则

\[\begin{align*} f(T)&=\prod_{k_1=0}^{e_1}\prod_{k_2=0}^{e_2}\dots\prod_{k_m=0}^{e_m}\left(\prod_{i=1}^mp_i^{k_i}\right)^{\mu\bigl(\prod_{j=1}^mp_j^{e_j}/\prod_{j=1}^mp_j^{k_j}\bigr)} \\ &=\prod_{k_1=0}^{e_1}\prod_{k_2=0}^{e_2}\dots\prod_{k_m=0}^{e_m}\left(\prod_{i=1}^mp_i^{k_i}\right)^{\mu\bigl(\prod_{j=1}^mp_j^{e_j-k_j}\bigr)} \\ &=\prod_{k_1=0}^{e_1}\prod_{k_2=0}^{e_2}\dots\prod_{k_m=0}^{e_m}\left(\prod_{i=1}^mp_i^{k_i}\right)^{\prod_{j=1}^m\mu\bigl(p_j^{e_j-k_j}\bigr)} \\ &=\prod_{k_1=0}^{e_1}\prod_{k_2=0}^{e_2}\dots\prod_{k_m=0}^{e_m}\prod_{i=1}^mp_i^{k_i\cdot\prod_{j=1}^m\mu\bigl(p_j^{e_j-k_j}\bigr)} \\ &=\prod_{i=1}^mp_i^{\sum_{k_1=0}^{e_1}\sum_{k_2=0}^{e_2}\dots\sum_{k_m=0}^{e_m}k_i\cdot\prod_{j=1}^m\mu\bigl(p_j^{e_j-k_j}\bigr)} \end{align*} \]

其中，当 \(m\geq2\) 时，指数

\[\begin{align*} &\sum_{k_1=0}^{e_1}\sum_{k_2=0}^{e_2}\dots\sum_{k_m=0}^{e_m}\left(k_i\cdot\prod_{j=1}^m\mu\!\left(p_j^{e_j-k_j}\right)\right) \\ =&\sum_{k_1=0}^{e_1}\sum_{k_2=0}^{e_2}\dots\sum_{k_m=0}^{e_m}\left(k_i\cdot\mu\!\left(p_i^{e_i-k_i}\right)\cdot\prod_{\substack{1\leq j\leq m\\[2pt]j\neq i}}\mu\!\left(p_j^{e_j-k_j}\right)\right) \\ =&\sum_{k_i=0}^{e_i}\left(\sum_{k_1=0}^{e_1}\dots\sum_{k_{i-1}=0}^{e_{i-1}}\sum_{k_{i+1}=0}^{e_{i+1}}\dots\sum_{k_m=0}^{e_m}\Biggl(k_i\cdot\mu\!\left(p_i^{e_i-k_i}\right)\Biggr)\left(\prod_{\substack{1\leq j\leq m\\[2pt]j\neq i}}\mu\!\left(p_j^{e_j-k_j}\right)\right)\right) \\ =&\sum_{0\leq k_i\leq e_i}\sum_{\substack{0\leq k_1\leq e_1 \\\dots\\0\leq k_{i-1}\leq e_{i-1}\\0\leq k_{i+1}\leq e_{i+1}\\\dots\\0\leq k_m\leq e_m}}\Biggl(k_i\cdot\mu\!\left(p_i^{e_i-k_i}\right)\Biggr)\left(\prod_{\substack{1\leq j\leq m\\[2pt]j\neq i}}\mu\!\left(p_j^{e_j-k_j}\right)\right) \\ =&\sum_{0\leq k_i\leq e_i}\Biggl(k_i\cdot\mu\!\left(p_i^{e_i-k_i}\right)\Biggr)\cdot\sum_{\substack{0\leq k_1\leq e_1 \\\dots\\0\leq k_{i-1}\leq e_{i-1}\\0\leq k_{i+1}\leq e_{i+1}\\\dots\\0\leq k_m\leq e_m}}\left(\prod_{\substack{1\leq j\leq m\\[2pt]j\neq i}}\mu\!\left(p_j^{e_j-k_j}\right)\right) \\ =&\sum_{k_i=0}^{e_i}\Biggl(k_i\cdot\mu\!\left(p_i^{e_i-k_i}\right)\Biggr)\left(\sum_{k_1=0}^{e_1}\dots\sum_{k_{i-1}=0}^{e_{i-1}}\sum_{k_{i+1}=0}^{e_{i+1}}\dots\sum_{k_m=0}^{e_m}\prod_{\substack{1\leq j\leq m\\[2pt]j\neq i}}\mu\!\left(p_j^{e_j-k_j}\right)\right) \end{align*} \]

在

\[\sum_{k_1=0}^{e_1}\dots\sum_{k_{i-1}=0}^{e_{i-1}}\sum_{k_{i+1}=0}^{e_{i+1}}\dots\sum_{k_m=0}^{e_m}\prod_{\substack{1\leq j\leq m\\[2pt]j\neq i}}\mu\!\left(p_j^{e_j-k_j}\right) \]

中：

• 若 \(e_j-k_j\geq2\)，则 \(\mu\!\left(p_j^{e_j-k_j}\right)=0\)，此时整个累乘的结果为 \(0\)，对最终的和贡献为 \(0\).

• 若 \(e_j-k_j=1\)，则 \(\mu\!\left(p_j^{e_j-k_j}\right)=\mu\!\left(p_j\right)=-1\).

• 若 \(e_j-k_j=0\)，则 \(\mu\!\left(p_j^{e_j-k_j}\right)=\mu(1)=1\).

• 上面两种情况的值互为相反数，在其他 \(k_j\) 相同时累乘结果互为相反数，对于最终的和的贡献互为相反数，因此它们对和的贡献为 \(0\).

因此指数为 \(0\). 此时，

\[f(T)=\prod_{i=1}^mp_i^0=\prod_{i=1}^m1=1 \]

当 \(m=1\) 即 \(T=p^e\) 时，上面指数的式子无法拆分，此时

\[\begin{align*} f(T)&=\prod_{d|T}d^{\mu(T/d)} \\ &=\prod_{k=0}^e\left(p^k\right)^{\mu(p^e/p^k)} \\ &=\prod_{k=0}^e\left(p^k\right)^{\mu(p^{e-k})} \end{align*} \]

当 \(e-k\geq2\) 时，\(\mu\!\left(p^{e-k}\right)=0\)，\(\left(p^k\right)^{\mu(p^{e-k})}=1\)，对累乘的结果没有影响. 因此

\[\begin{align*} f(T)&=\prod_{k=e-1}^e\left(p^k\right)^{\mu(p^{e-k})} \\ &=\left(p^{e-1}\right)^{\mu(p^1)}\cdot\left(p^e\right)^{\mu(p^0)} \\ &=\left(p^{e-1}\right)^{-1}\cdot p^e \\ &=p^{-e+1}\cdot p^e \\ &=p \end{align*} \]

关于 \(f(T)\) 的讨论到此结束. 我们最终得出了

\[f(T)= \begin{cases} p,&T=p^k \\ 1,&\text{otherwise} \end{cases} \]

于是可以使用欧拉筛以 \(O(N)\) 的时间复杂度预处理 \(f(x)\).

\[\begin{align*} F_0(A,B,C)=&\left(\prod_{T=1}^{\min(A,B)}\left(\prod_{d|T}d^{\mu(T/d)}\right)^{\lfloor A/T\rfloor\cdot\lfloor B/T\rfloor}\right)^C \\ =&\left(\prod_{T=1}^{\min(A,B)}f(T)^{\lfloor A/T\rfloor\cdot\lfloor B/T\rfloor}\right)^C \end{align*} \]

预处理 \(f(T)\) 的前缀积，这样就可以使用整除分块的技巧，以

\[O\!\left(\sqrt{N}\log P\right) \]

的时间复杂度回答单次询问. \(\left\lfloor\frac{A}{T}\right\rfloor\!\cdot\!\left\lfloor\frac{B}{T}\right\rfloor\) 最大可以达到 \(N^2\gg P\)，因为 \(P\) 为质数，\(f(T)\) 是多个不大于 \(T\) 的正整数相乘得到的，且 \(T\leq N<P\)，所以底数与模数互质，所以指数可以直接对 \(P-1\) 取模（费马小定理降幂）. 这就是时间复杂度式子中 \(\log P\) 的出处.

type=1

\(G_1(A,B,C)\)

\[\begin{align*} G_1(A,B,C)&=\prod_{i=1}^Ai^{\sum_{j=1}^B\sum_{k=1}^Cf(type)} \\ &=\prod_{i=1}^Ai^{\sum_{j=1}^B\sum_{k=1}^Cijk} \\ &=\prod_{i=1}^Ai^{i\cdot\sum_{j=1}^Bj\cdot\sum_{k=1}^Ck} \\ &=\prod_{i=1}^Ai^{i\cdot\frac{B(B+1)}{2}\cdot\frac{C(C+1)}{2}} \\ &=\left(\prod_{i=1}^Ai^i\right)^{\frac{B(B+1)}{2}\cdot\frac{C(C+1)}{2}} \end{align*} \]

需要快速幂预处理 \(\prod_{i=1}^Ni^i\)，时间复杂度 \(O(N\log N)\).

\(F_1(A,B,C)\)

\[\begin{align*} F_1(A,B,C)&=\prod_{i=1}^A\prod_{j=1}^B\gcd(i,j)^{\sum_{k=1}^Cf(type)} \\ &=\prod_{i=1}^A\prod_{j=1}^B\gcd(i,j)^{\sum_{k=1}^Cijk} \\ &=\prod_{i=1}^A\prod_{j=1}^B\gcd(i,j)^{ij\cdot\sum_{k=1}^Ck} \\ &=\prod_{i=1}^A\prod_{j=1}^B\gcd(i,j)^{ij\cdot\frac{C(C+1)}{2}} \\ &=\left(\prod_{i=1}^A\prod_{j=1}^B\gcd(i,j)^{ij}\right)^{\frac{C(C+1)}{2}} \\ &=\left(\prod_{d=1}^{\min(A,B)}\prod_{\substack{1\leq i\leq A\\[2pt]1\leq j\leq B\\[2pt]\gcd(i,j)=d}}d^{ij}\right)^{\frac{C(C+1)}{2}} \\ &=\left(\prod_{d=1}^{\min(A,B)}\prod_{\substack{1\leq di\leq A\\[2pt]1\leq dj\leq B\\[2pt]\gcd(di,dj)=d}}d^{di\cdot dj}\right)^{\frac{C(C+1)}{2}} \\ &=\left(\prod_{d=1}^{\min(A,B)}\prod_{\substack{1\leq i\leq\lfloor A/d\rfloor\\[2pt]1\leq j\leq\lfloor B/d\rfloor\\[2pt]\gcd(i,j)=1}}d^{d^2ij}\right)^{\frac{C(C+1)}{2}} \\ &=\left(\prod_{d=1}^{\min(A,B)}d^{\sum_{i=1}^{\lfloor A/d\rfloor}\sum_{j=1}^{\lfloor B/d\rfloor}[\gcd(i,j)=1]\cdot d^2ij}\right)^{\frac{C(C+1)}{2}} \end{align*} \]

其中，

\[\begin{align*} &\sum_{i=1}^{\lfloor A/d\rfloor}\sum_{j=1}^{\lfloor B/d\rfloor}\bigl[\gcd(i,j)=1\bigr]\cdot ij \\ =&\sum_{i=1}^{\lfloor A/d\rfloor}\sum_{j=1}^{\lfloor B/d\rfloor}\sum_{x|i,\,x|j}\mu(x)\cdot ij \\ =&\sum_{i=1}^{\lfloor A/d\rfloor}\sum_{j=1}^{\lfloor B/d\rfloor}ij\cdot\sum_{x|i,\,x|j}\mu(x) \\ =&\sum_{x=1}^{\min(\lfloor A/d\rfloor,\lfloor B/d\rfloor)}\mu(x)\cdot\sum_{i=1}^{\lfloor\frac{A}{dx}\rfloor}\sum_{j=1}^{\lfloor\frac{B}{dx}\rfloor}xi\cdot xj \\ =&\sum_{x=1}^{\min(\lfloor A/d\rfloor,\lfloor B/d\rfloor)}x^2\cdot\mu(x)\cdot\sum_{i=1}^{\lfloor\frac{A}{dx}\rfloor}\sum_{j=1}^{\lfloor\frac{B}{dx}\rfloor}ij \\ =&\sum_{x=1}^{\min(\lfloor A/d\rfloor,\lfloor B/d\rfloor)}x^2\cdot\mu(x)\cdot\sum_{i=1}^{\lfloor\frac{A}{dx}\rfloor}i\cdot\sum_{j=1}^{\lfloor\frac{B}{dx}\rfloor}j \end{align*} \]

令

\[S(n)=\sum_{i=1}^ni=\frac{n(n+1)}{2} \]

则

\[\begin{align*} &\sum_{x=1}^{\min(\lfloor A/d\rfloor,\lfloor B/d\rfloor)}x^2\cdot\mu(x)\cdot\sum_{i=1}^{\lfloor\frac{A}{dx}\rfloor}i\cdot\sum_{j=1}^{\lfloor\frac{B}{dx}\rfloor}j \\ =&\sum_{x=1}^{\min(\lfloor A/d\rfloor,\lfloor B/d\rfloor)}x^2\cdot\mu(x)\cdot S\!\left(\frac{A}{dx}\right)\cdot S\!\left(\frac{B}{dx}\right) \end{align*} \]

令 \(T=dx\)，则 \(x=\frac{T}{d}\).

则

\[\begin{align*} F_1(A,B,C)&=\left(\prod_{d=1}^{\min(A,B)}d^{d^2\cdot\sum_{i=1}^{\lfloor A/d\rfloor}\sum_{j=1}^{\lfloor B/d\rfloor}[\gcd(i,j)=1]\cdot ij}\right)^{\frac{C(C+1)}{2}} \\ &=\left(\prod_{d=1}^{\min(A,B)}d^{d^2\cdot\sum_{x=1}^{\min(\lfloor A/d\rfloor,\lfloor B/d\rfloor)}x^2\cdot\mu(x)\cdot S(\frac{A}{dx})\cdot S(\frac{B}{dx})}\right)^{\frac{C(C+1)}{2}} \\ &=\left(\prod_{T=1}^{\min(A,B)}\prod_{d|T}d^{d^2\cdot(T/d)^2\cdot\mu(T/d)\cdot S(A/T)\cdot S(B/T)}\right)^{\frac{C(C+1)}{2}} \\ &=\left(\prod_{T=1}^{\min(A,B)}\prod_{d|T}d^{T^2\cdot\mu(T/d)\cdot S(A/T)\cdot S(B/T)}\right)^{\frac{C(C+1)}{2}} \\ &=\left(\prod_{T=1}^{\min(A,B)}\left(\prod_{d|T}d^{\mu(T/d)}\right)^{T^2\cdot S(A/T)\cdot S(B/T)}\right)^{\frac{C(C+1)}{2}} \\ &=\left(\prod_{T=1}^{\min(A,B)}f(T)^{T^2\cdot S(A/T)\cdot S(B/T)}\right)^{\frac{C(C+1)}{2}} \\ &=\left(\prod_{T=1}^{\min(A,B)}\left(f(T)^{T^2}\right)^{S(A/T)\cdot S(B/T)}\right)^{\frac{C(C+1)}{2}} \end{align*} \]

现在需要预处理 \(f(T)^{T^2}\). 前面推出

\[f(T)= \begin{cases} p,&T=p^k \\ 1,&\text{otherwise} \end{cases} \]

当 \(T\neq p^k\) 即 \(f(T)=1\) 时，\(f(T)^{T^2}=1\)，单独计算时间复杂度为 \(O(1)\).

当 \(T=p^k\) 时，单独计算时间复杂度为 \(O(\log P)\)（费马小定理降幂）. 质数幂在 \([1,N]\) 中的密度约为 \(\frac{1}{\ln N}\)，因此预处理 \(f(T)^{T^2}\) 的时间复杂度为

\[O\!\left(\frac{N}{\log N}\cdot\log P\right) \]

这是几乎线性的，而当 \(\frac{\log P}{\log N}\) 很大时，\(N\) 必然很小.

于是可以用整除分块以 \(O(\sqrt{N}\log P)\) 的时间复杂度回答单次询问.

type=2

\(G_2(A,B,C)\)

\[\begin{align*} G_2(A,B,C)&=\prod_{i=1}^Ai^{\sum_{j=1}^B\sum_{k=1}^Cf(type)} \\ &=\prod_{i=1}^Ai^{\sum_{j=1}^B\sum_{k=1}^C\gcd(i,j,k)} \\ &=\prod_{i=1}^A\prod_{d|i}i^{\sum_{j=1}^B\sum_{k=1}^Cd\cdot[\gcd(i,j,k)=d]} \\ &=\prod_{d=1}^A\prod_{i=1}^{\lfloor A/d\rfloor}(di)^{d\cdot\sum_{j=1}^B\sum_{k=1}^C[\gcd(di,j,k)=d]} \\ &=\prod_{d=1}^A\prod_{i=1}^{\lfloor A/d\rfloor}(di)^{d\cdot\sum_{j=1}^{\lfloor B/d\rfloor}\sum_{k=1}^{\lfloor C/d\rfloor}[\gcd(i,j,k)=1]} \\ &=\prod_{d=1}^A\prod_{i=1}^{\lfloor A/d\rfloor}(di)^{d\cdot\sum_{j=1}^{\lfloor B/d\rfloor}\sum_{k=1}^{\lfloor C/d\rfloor}\sum_{x|i,x|j,x|k}\mu(x)} \\ &=\prod_{d=1}^A\prod_{i=1}^{\lfloor A/d\rfloor}(di)^{d\cdot\sum_{1\leq x\leq\min(\lfloor B/d\rfloor,\lfloor C/d\rfloor),\,x|i}\mu(x)\cdot\sum_{j=1}^{\lfloor B/(dx)\rfloor}\sum_{k=1}^{\lfloor C/(dx)\rfloor}1} \\ &=\prod_{d=1}^A\prod_{i=1}^{\lfloor A/d\rfloor}(di)^{d\cdot\sum_{1\leq x\leq\min(\lfloor B/d\rfloor,\lfloor C/d\rfloor),\,x|i}\mu(x)\cdot\lfloor\frac{B}{dx}\rfloor\cdot\lfloor\frac{C}{dx}\rfloor} \\ &=\prod_{d=1}^A\prod_{x=1}^{\min(\lfloor A/d\rfloor,\lfloor B/d\rfloor,\lfloor C/d\rfloor)}\prod_{i=1}^{\lfloor\frac{A}{dx}\rfloor}(di)^{d\cdot\mu(x)\cdot\lfloor\frac{B}{dx}\rfloor\cdot\lfloor\frac{C}{dx}\rfloor} \\ &=\prod_{d=1}^A\prod_{x=1}^{\min(\lfloor A/d\rfloor,\lfloor B/d\rfloor,\lfloor C/d\rfloor)}\prod_{i=1}^{\lfloor\frac{A}{dx}\rfloor}(dxi)^{d\cdot\mu(x)\cdot\lfloor\frac{B}{dx}\rfloor\cdot\lfloor\frac{C}{dx}\rfloor} \\ &=\prod_{T=1}^{\min(A,B,C)}\prod_{d|T}\prod_{i=1}^{\lfloor A/T\rfloor}(Ti)^{d\cdot\mu(T/d)\cdot\lfloor B/T\rfloor\cdot\lfloor C/T\rfloor} \\ &=\prod_{T=1}^{\min(A,B,C)}\prod_{d|T}\left(\prod_{i=1}^{\lfloor A/T\rfloor}Ti\right)^{d\cdot\mu(T/d)\cdot\lfloor B/T\rfloor\cdot\lfloor C/T\rfloor} \\ &=\prod_{T=1}^{\min(A,B,C)}\left(\prod_{d|T}\left(\prod_{i=1}^{\lfloor A/T\rfloor}Ti\right)^{d\cdot\mu(T/d)}\right)^{\lfloor B/T\rfloor\cdot\lfloor C/T\rfloor} \\ &=\prod_{T=1}^{\min(A,B,C)}\left(\prod_{d|T}\left(T^{\lfloor A/T\rfloor}\cdot\prod_{i=1}^{\lfloor A/T\rfloor}i\right)^{d\cdot\mu(T/d)}\right)^{\lfloor B/T\rfloor\cdot\lfloor C/T\rfloor} \\ &=\prod_{T=1}^{\min(A,B,C)}\left(\left(T^{\lfloor A/T\rfloor}\cdot\prod_{i=1}^{\lfloor A/T\rfloor}i\right)^{\sum_{d|T}d\cdot\mu(T/d)}\right)^{\lfloor B/T\rfloor\cdot\lfloor C/T\rfloor} \\ &=\prod_{T=1}^{\min(A,B,C)}\left(\left(T^{\lfloor A/T\rfloor}\cdot\prod_{i=1}^{\lfloor A/T\rfloor}i\right)^{\varphi(T)}\right)^{\lfloor B/T\rfloor\cdot\lfloor C/T\rfloor} \\ &=\prod_{T=1}^{\min(A,B,C)}\left(T^{\lfloor A/T\rfloor}\cdot\prod_{i=1}^{\lfloor A/T\rfloor}i\right)^{\varphi(T)\cdot\lfloor B/T\rfloor\cdot\lfloor C/T\rfloor} \end{align*} \]

进一步展开已经意义不大了.

对于 \(T^{\lfloor A/T\rfloor}\)：预处理 \(T\) 的前缀积.

对于 \(\prod_{i=1}^{\lfloor A/T\rfloor}\)：在 \(\text{type}=0\) 中已经预处理过了阶乘.

剩下的就是实现细节了.

使用整除分块的技巧，对于每一块 \(\left\lfloor\frac{A}{T}\right\rfloor\)，\(\left\lfloor\frac{B}{T}\right\rfloor\)，\(\left\lfloor\frac{C}{T}\right\rfloor\) 各自不变，需要做若干次快速幂，回答单次询问时间复杂度为 \(O(\sqrt{N}\log P)\).

\(F_2(A,B,C)\)

\[\begin{align*} &F_2(A,B,C) \\ =&\prod_{i=1}^A\prod_{j=1}^B\gcd(i,j)^{\sum_{k=1}^Cf(type)} \\ =&\prod_{i=1}^A\prod_{j=1}^B\gcd(i,j)^{\sum_{k=1}^C\gcd(i,j,k)} \\ =&\prod_{i=1}^A\prod_{j=1}^B\gcd(i,j)^{\sum_{k=1}^C\gcd(\gcd(i,j),k)} \\ =&\prod_{i=1}^A\prod_{j=1}^B\prod_{d|i,\,d|j}d^{[\gcd(i,j)=d]\cdot\sum_{k=1}^C\gcd(d,k)} \\ =&\prod_{d=1}^{\min(A,B)}\prod_{i=1}^{\lfloor A/d\rfloor}\prod_{j=1}^{\lfloor B/d\rfloor}d^{[\gcd(di,dj)=d]\cdot\sum_{k=1}^C\sum_{s|d,s|k}\varphi(s)} \\ =&\prod_{d=1}^{\min(A,B)}\prod_{i=1}^{\lfloor A/d\rfloor}\prod_{j=1}^{\lfloor B/d\rfloor}d^{[\gcd(i,j)=1]\cdot\sum_{s|d}\varphi(s)\cdot\sum_{k=1}^{\lfloor C/s\rfloor}1} \\ =&\prod_{d=1}^{\min(A,B)}\prod_{i=1}^{\lfloor A/d\rfloor}\prod_{j=1}^{\lfloor B/d\rfloor}d^{[\gcd(i,j)=1]\cdot\sum_{s|d}\varphi(s)\cdot\lfloor\frac{C}{s}\rfloor} \\ =&\prod_{d=1}^{\min(A,B)}d^{\sum_{i=1}^{\lfloor A/d\rfloor}\sum_{j=1}^{\lfloor B/d\rfloor}[\gcd(i,j)=1]\cdot\sum_{s|d}\varphi(s)\cdot\lfloor\frac{C}{s}\rfloor} \\ =&\prod_{d=1}^{\min(A,B)}d^{\sum_{i=1}^{\lfloor A/d\rfloor}\sum_{j=1}^{\lfloor B/d\rfloor}\sum_{x|i,x|j}\mu(x)\cdot\sum_{s|d}\varphi(s)\cdot\lfloor\frac{C}{s}\rfloor} \\ =&\prod_{d=1}^{\min(A,B)}d^{\sum_{x=1}^{\lfloor\min(A,B)/d\rfloor}\mu(x)\cdot\sum_{i=1}^{\lfloor A/dx\rfloor}\sum_{j=1}^{\lfloor B/dx\rfloor}1\cdot\sum_{s|d}\varphi(s)\cdot\lfloor\frac{C}{s}\rfloor} \\ =&\prod_{d=1}^{\min(A,B)}d^{\sum_{s|d}\varphi(s)\cdot\lfloor\frac{C}{s}\rfloor\cdot\sum_{x=1}^{\lfloor\min(A,B)/d\rfloor}\mu(x)\cdot\lfloor\frac{A}{dx}\rfloor\cdot\lfloor\frac{B}{dx}\rfloor} \\ =&\prod_{d=1}^{\min(A,B)}\prod_{s|d}d^{\varphi(s)\cdot\lfloor\frac{C}{s}\rfloor\cdot\sum_{x=1}^{\lfloor\min(A,B)/d\rfloor}\mu(x)\cdot\lfloor\frac{A}{dx}\rfloor\cdot\lfloor\frac{B}{dx}\rfloor} \\ =&\prod_{s=1}^{\min(A,B)}\prod_{d=1}^{\lfloor\min(A,B)/s\rfloor}(ds)^{\varphi(s)\cdot\lfloor\frac{C}{s}\rfloor\cdot\sum_{x=1}^{\lfloor\min(A,B)/ds\rfloor}\cdot\mu(x)\cdot\lfloor\frac{A}{dsx}\rfloor\cdot\lfloor\frac{B}{dsx}\rfloor} \\ =&\prod_{s=1}^{\min(A,B)}\prod_{d=1}^{\lfloor\min(A,B)/s\rfloor}\prod_{x=1}^{\lfloor\min(A,B)/ds\rfloor}(ds)^{\varphi(s)\cdot\lfloor\frac{C}{s}\rfloor\cdot\mu(x)\cdot\lfloor\frac{A}{dsx}\rfloor\cdot\lfloor\frac{B}{dsx}\rfloor} \\ =&\prod_{s=1}^{\min(A,B)}\prod_{T=1}^{\lfloor\min(A,B)/s\rfloor}\prod_{d|T}(ds)^{\mu(T/d)\cdot\lfloor\frac{A}{sT}\rfloor\cdot\lfloor\frac{B}{sT}\rfloor\cdot\varphi(s)\cdot\lfloor\frac{C}{s}\rfloor} \\ =&\prod_{s=1}^{\min(A,B)}\prod_{T=1}^{\lfloor\min(A,B)/s\rfloor}\prod_{d|T}d^{\mu(T/d)\cdot\lfloor\frac{A}{sT}\rfloor\cdot\lfloor\frac{B}{sT}\rfloor\cdot\varphi(s)\cdot\lfloor\frac{C}{s}\rfloor}\cdot\prod_{s=1}^{\min(A,B)}\prod_{T=1}^{\lfloor\min(A,B)/s\rfloor}\prod_{d|T}s^{\mu(T/d)\cdot\lfloor\frac{A}{sT}\rfloor\cdot\lfloor\frac{B}{sT}\rfloor\cdot\varphi(s)\cdot\lfloor\frac{C}{s}\rfloor} \\ =&\prod_{s=1}^{\min(A,B)}\left(\prod_{T=1}^{\lfloor\min(A,B)/s\rfloor}\left(\prod_{d|T}d^{\mu(T/d)}\right)^{\lfloor\frac{A}{sT}\rfloor\cdot\lfloor\frac{B}{sT}\rfloor}\right)^{\varphi(s)\cdot\lfloor\frac{C}{s}\rfloor}\cdot\prod_{s=1}^{\min(A,B)}\prod_{T=1}^{\lfloor\min(A,B)/s\rfloor}s^{\sum_{d|T}\mu(T/d)\cdot\lfloor\frac{A}{sT}\rfloor\cdot\lfloor\frac{B}{sT}\rfloor\cdot\varphi(s)\cdot\lfloor\frac{C}{s}\rfloor} \end{align*} \]

对于左边的乘数：

之前推出了

\[F_0(A,B,C)=\left(\prod_{T=1}^{\min(A,B)}\left(\prod_{d|T}d^{\mu(T/d)}\right)^{\lfloor A/T\rfloor\cdot\lfloor B/T\rfloor}\right)^C \]

可以发现它和上面的结果结构几乎相同，即

\[\left(\prod_{T=1}^{\lfloor\min(A,B)/s\rfloor}\left(\prod_{d|T}d^{\mu(T/d)}\right)^{\lfloor\frac{A}{sT}\rfloor\cdot\lfloor\frac{B}{sT}\rfloor}\right)^{\varphi(s)\cdot\lfloor\frac{C}{s}\rfloor}=F_0\!\left(\left\lfloor\frac{A}{s}\right\rfloor,\;\left\lfloor\frac{B}{s}\right\rfloor,\;\varphi(s)\left\lfloor\frac{C}{s}\right\rfloor\right) \]

于是

\[\prod_{s=1}^{\min(A,B)}\left(\prod_{T=1}^{\lfloor\min(A,B)/s\rfloor}\left(\prod_{d|T}d^{\mu(T/d)}\right)^{\lfloor\frac{A}{sT}\rfloor\cdot\lfloor\frac{B}{sT}\rfloor}\right)^{\varphi(s)\cdot\lfloor\frac{C}{s}\rfloor}=\prod_{s=1}^{\min(A,B)}F_0\!\left(\left\lfloor\frac{A}{s}\right\rfloor,\;\left\lfloor\frac{B}{s}\right\rfloor,\;\varphi(s)\left\lfloor\frac{C}{s}\right\rfloor\right) \]

这是可以整除分块的.

其中，求

\[F_0\!\left(\left\lfloor\frac{A}{s}\right\rfloor,\;\left\lfloor\frac{B}{s}\right\rfloor,\;\varphi(s)\left\lfloor\frac{C}{s}\right\rfloor\right) \]

的时间复杂度为

\[O\!\left(\sqrt{\min\!\left(\frac{A}{s},\,\frac{B}{s}\right)}\log P\right) \]

于是，总体整除分块的时间复杂度为

\[O\!\left(\sum_{i=1}^{\sqrt{N}}\sqrt{i}\log P+\sum_{i=1}^{\sqrt{N}}\sqrt{\frac{N}{i}}\log P\right) \]

即

\[O\!\left(N^{3/4}\log P\right) \]

对于右边的乘数：

\[\begin{align*} &\prod_{s=1}^{\min(A,B)}\prod_{T=1}^{\lfloor\min(A,B)/s\rfloor}s^{\sum_{d|T}\mu(T/d)\cdot\lfloor\frac{A}{sT}\rfloor\cdot\lfloor\frac{B}{sT}\rfloor\cdot\varphi(s)\cdot\lfloor\frac{C}{s}\rfloor} \\ =&\prod_{s=1}^{\min(A,B)}\prod_{T=1}^{\lfloor\min(A,B)/s\rfloor}s^{\sum_{d|T}\mu(d)\cdot\lfloor\frac{A}{sT}\rfloor\cdot\lfloor\frac{B}{sT}\rfloor\cdot\varphi(s)\cdot\lfloor\frac{C}{s}\rfloor} \\ =&\prod_{s=1}^{\min(A,B)}\prod_{T=1}^{\lfloor\min(A,B)/s\rfloor}s^{\varepsilon(T)\cdot\lfloor\frac{A}{sT}\rfloor\cdot\lfloor\frac{B}{sT}\rfloor\cdot\varphi(s)\cdot\lfloor\frac{C}{s}\rfloor} \\ =&\prod_{s=1}^{\min(A,B)}s^{\varepsilon(1)\cdot\lfloor\frac{A}{s}\rfloor\cdot\lfloor\frac{B}{s}\rfloor\cdot\varphi(s)\cdot\lfloor\frac{C}{s}\rfloor} \\ =&\prod_{s=1}^{\min(A,B,C)}s^{\varphi(s)\cdot\lfloor\frac{A}{s}\rfloor\cdot\lfloor\frac{B}{s}\rfloor\cdot\lfloor\frac{C}{s}\rfloor} \end{align*} \]

可以用整除分块以 \(O(\sqrt{N}\log P)\) 的时间复杂度回答单次询问.

最终

\[F_2(A,B,C)=\prod_{s=1}^{\min(A,B)}s^{\varphi(s)\cdot\lfloor\frac{A}{s}\rfloor\cdot\lfloor\frac{B}{s}\rfloor\cdot\lfloor\frac{C}{s}\rfloor}\cdot F_0\!\left(\left\lfloor\frac{A}{s}\right\rfloor,\;\left\lfloor\frac{B}{s}\right\rfloor,\;\varphi(s)\left\lfloor\frac{C}{s}\right\rfloor\right) \]

回答单次询问的总共的时间复杂度是 \(O\!\left(N^{3/4}\log P\right)\).

总共时间复杂度

预处理：\(O(N\log N)\)

回答单次询问：\(O\!\left(N^{3/4}\log P\right)\)

足以通过本题.

优化

以下关于 \(\log\) 的数值计算默认以 \(2\) 为底（快速幂）.

注意到预处理时间复杂度是 \(O(N\log N)\) 的，而回答询问总共的时间复杂度为 \(O\!\left(T\cdot N^{3/4}\log P\right)\).

题目中最大 \(N=10^5\)，\(T=70\)，\(P\approx 10^9\).

预处理：\(N\log N\approx 1.66\times 10^6\)

查询：\(T\cdot N^{3/4}\log P\approx 1.18\times 10^7\)

即使不考虑常数因子的影响，差距也是悬殊的.

查询的瓶颈在于 \(\text{type}=2\) 的整除分块，而整除分块中计算每一块的瓶颈在于 \(F_0(\dots)\).

接下来分析整除分块的 \(\left\lfloor\frac{N}{i}\right\rfloor\) 在 \(i\in[1,N]\) 上的分布. 这实际上是一个反比例函数，令 \(x\) 轴上为 \(i\)，\(y\) 轴上为 \(\frac{N}{i}\)，当 \(i\) 取值小时，函数图像陡峭（\(y\) 轴覆盖值域广），此时相应的 \(y\) 值较大；当 \(i\) 取值大时，函数图像平缓（\(y\) 轴覆盖值域窄），此时相应的 \(y\) 值较小. 因此 \(\left\lfloor\frac{N}{i}\right\rfloor\) 在值较小处分布密集，在值较大处分布稀疏.

因为

\[F_0(A,B,C)=\left(\prod_{T=1}^{\min(A,B)}f(T)^{\lfloor A/T\rfloor\cdot\lfloor B/T\rfloor}\right)^C \]

跟 \(C\) 关系不大，所以我们预处理 \(A,B\leq K\) 时的

\[\prod_{T=1}^{\min(A,B)}f(T)^{\lfloor A/T\rfloor\cdot\lfloor B/T\rfloor} \]

用到时加上一个 \(\log P\) 的快速幂即可. 接下来分析当 \(K\) 取多少时，预处理的时间复杂度和查询的时间复杂度持平（此时两者之和最小）.

预处理

之前推出

\[F_0(A,B,C)=\left(\prod_{i=1}^A\prod_{j=1}^B\gcd(i,j)\right)^C=\left(\prod_{T=1}^{\min(A,B)}f(T)^{\lfloor A/T\rfloor\cdot\lfloor B/T\rfloor}\right)^C \]

所以，设

\[g(A,B)=\prod_{T=1}^{\min(A,B)}f(T)^{\lfloor A/T\rfloor\cdot\lfloor B/T\rfloor}=\prod_{i=1}^A\prod_{j=1}^B\gcd(i,j) \]

其实 \(g(A,B)\) 就是 \(\gcd(i,j)\) 的二维前缀积. 因此

\[g(A,B)=g(A-1,B)\cdot g(A,B-1)\cdot g^{-1}(A-1,B-1)\cdot\gcd(A,B) \]

边界条件：\(g(x,0)=g(0,x)=1\).

其中，对于 \(g(A-1,B-1)^{-1}\)，我们可以同步处理逆元，\(g^{-1}\) 就是 \(\gcd^{-1}(i,j)\) 的二维前缀积，即

\[g^{-1}(A,B)=g^{-1}(A-1,B)\cdot g^{-1}(A,B-1)\cdot g(A-1,B-1)\cdot\operatorname{gcd}^{-1}(A,B) \]

对于 \(\gcd(A,B)\)，显然 \(\gcd(A,B)=\gcd(B,A)\)，于是只预处理 \(A\geq B\) 的情况，对此我们有经典辗转互除法：

\[\gcd(A,B)=\gcd(B,A\bmod B) \]

其中 \(\gcd(A,0)=A\).

由于 \(\gcd(A,B)\leq\min(A,B)\leq N\)，即 \(\gcd(A,B)\) 的值域为 \(N\)，所以我们对于 \([1,N]\) 的每个数预处理逆元，直接费马小定理快速幂以 \(O(N\log P)\) 的时间复杂度预处理即可.

于是 \(g\) 和 \(g^{-1}\) 的单次转移都是 \(O(1)\) 的.

最终，预处理 \(g(A,B)\;(1\leq A,B\leq K)\) 的时间复杂度为 \(O(K^2)\).

查询

在

\[\prod_{s=1}^{\min(A,B)}F_0\!\left(\left\lfloor\frac{A}{s}\right\rfloor,\;\left\lfloor\frac{B}{s}\right\rfloor,\;\varphi(s)\left\lfloor\frac{C}{s}\right\rfloor\right) \]

中，不妨设 \(A=B=C=N\)，于是该式变为

\[\prod_{s=1}^Ng\!\left(\left\lfloor\frac{N}{s}\right\rfloor,\;\left\lfloor\frac{N}{s}\right\rfloor\right)^{\varphi(s)\lfloor C/s\rfloor} \]

先不考虑指数的快速幂.

对于 \(\frac{N}{s}\leq K\) 即 \(s\geq\frac{N}{K}\) 的部分，直接 \(O(1)\) 查表即可，块数最大为 \(O\bigl(\min(K,\sqrt{N})\bigr)\).

对于 \(s<\frac{N}{K}\) 的部分，时间复杂度约为

\[O\!\left(\sum_{s=1}^{N/K}\sqrt{\frac{N}{s}}\right) \]

上限约为

\[O\!\left(\frac{N}{\sqrt{K}}\right) \]

再乘上快速幂的 \(\log P\)，于是最终时间复杂度为

\[O\!\left(\left(\frac{N}{\sqrt{K}}+\min\!\left(K,\sqrt{N}\right)\right)\log P\right) \]

综合

预处理：\(O(K^2)\)

查询：\(O\!\left(T\cdot\left(\frac{N}{\sqrt{K}}+\min\!\left(K,\sqrt{N}\right)\right)\log P\right)\)

两者相等，即

\[K^2=T\cdot\left(\frac{N}{\sqrt{K}}+\min\!\left(K,\sqrt{N}\right)\right)\log P \]

将题目的数据范围代入，解方程，\(K\approx 2250\). 实际上，由于 \(K^2\) 的常数极小而右边的常数较大，将 \(K\) 设为 \(3000\) 是实践中的最好选择.

当 \(K=3000\) 时，预处理和总查询的时间复杂度都是 \(9\times 10^6\) 级别的，可以更快地通过本题.