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\) 级别的，可以更快地通过本题.