简要题意
计算
\[\prod_{i=1}^{A}\prod_{j=1}^{B}\prod_{k=1}^{C}\left(\frac{\text{lcm}(i,j)}{\gcd(i,k)}\right)^{f(type)} \]其中：
\[\begin{aligned} f(0)&=1 \cr f(1)&=i \times j \times k \cr f(2)&=\gcd(i,j,k) \end{aligned}\]\(T\) 组数据，每组数据给出 \(A,B,C\)，输出在 \(\text{type}=0,1,2\) 的值，对预先给出的质数 \(p\) 取模。
思路
魔鬼乐团……没看 tj 切黑题系列。
type=0
\[\prod_{i=1}^{A}\prod_{j=1}^{B}\prod_{k=1}^{C}\left(\frac{\text{lcm}(i,j)}{\gcd(i,k)}\right) \]原式取 \(\log\) 得：
\[\begin{aligned} &A\leq B\leq C\\ &\sum_{i=1}^{A}\sum_{j=1}^{B}\sum_{k=1}^{C}\log(\operatorname{lcm}(i,j))-\log(\gcd(i,k))\\ &=C\sum_{i=1}^{A}\sum_{j=1}^{B}\log(\operatorname{lcm}(i,j))-B\sum_{i=1}^{A}\sum_{k=1}^{C}\log(\gcd(i,k))\\ &=C\sum_{i=1}^{A}\sum_{j=1}^{B}\log(i)+\log(j)-\log(\gcd(i,j))-\\&\ B(\sum_{d=1}^{A}\lfloor\frac{A}{d}\rfloor\lfloor\frac{C}{d}\rfloor\sum_{k|d}\mu(\frac{d}{k})\log(k))\\ &=C\sum_{i=1}^{A}\sum_{j=1}^{B}\log(i)+C\sum_{i=1}^{B}\sum_{j=1}^{A}\log(i)-\\&C(\sum_{d=1}^{A}\lfloor\frac{A}{d}\rfloor\lfloor\frac{B}{d}\rfloor\sum_{k|d}\mu(\frac{d}{k})\log(k))-B(\sum_{d=1}^{A}\lfloor\frac{A}{d}\rfloor\lfloor\frac{C}{d}\rfloor\sum_{k|d}\mu(\frac{d}{k})\log(k))\\ &F(d)=\sum_{k|d}\mu(\frac{d}{k})\log(k))\\ &=BC\log(A!)+AC\log(B!)-C(\sum_{d=1}^{A}\lfloor\frac{A}{d}\rfloor\lfloor\frac{B}{d}\rfloor F(d))-B(\sum_{d=1}^{A}\lfloor\frac{A}{d}\rfloor\lfloor\frac{C}{d}\rfloor F(d)) \end{aligned} \]现在的式子取 \(\exp\)
\[\begin{aligned} &f(d)=\exp(F)=\prod_{k|d}\mu(k)^{\frac{d}{k}}\\ &=(A!)^{BC}\cdot(B!)^{AC}\cdot\dfrac{1}{C(\prod_{d=1}^{A}f(d)^{\lfloor\frac{A}{d}\rfloor\lfloor\frac{B}{d}\rfloor})\cdot B(\prod_{d=1}^{A}f(d)^{\lfloor\frac{A}{d}\rfloor\lfloor\frac{C}{d}\rfloor}} \end{aligned} \]type=1
\[\begin{aligned} &\prod_{i=1}^{A}\prod_{j=1}^{B}\prod_{k=1}^{C}\left(\frac{\text{lcm}(i,j)}{\gcd(i,k)}\right)^{ijk}\\ &F=\prod_{i=1}^{A}\prod_{j=1}^{B}\prod_{k=1}^{C}(ij)^{ijk},G(x,y)=\prod_{i=1}^{A}\prod_{j=1}^{x}\prod_{k=1}^{y}\gcd(i,j)^{ijk}\\ &=\frac{F}{G(B,C)G(C,B)} \end{aligned} \]先推 \(F\)：
\[\begin{aligned} &F=\prod_{i=1}^{A}\prod_{j=1}^{B}\prod_{k=1}^{C}(ij)^{ijk}\\ &=\prod_{i=1}^{A}\prod_{j=1}^{B}\prod_{k=1}^{C}i^{ijk}\cdot\prod_{i=1}^{A}\prod_{j=1}^{B}\prod_{k=1}^{C}j^{ijk}\\ &=\prod_{i=1}^{A}i^{\sum_{j=1}^{B}j\cdot\sum_{k=1}^{C}k}\cdot\prod_{i=1}^{B}i^{\sum_{j=1}^{A}j\cdot\sum_{k=1}^{C}k}\\ &W(x)=\sum_{i=1}^{x}i=\frac{x(x+1)}{2}\\ &=\prod_{i=1}^{A}i^{W(B)W(C)}\cdot\prod_{i=1}^{B}i^{W(A)W(C)}\\ &=(A!)^{W(B)W(C)}\cdot(B!)^{W(A)W(C)} \end{aligned} \]然后是 \(G\)，取 \(g=\log(G)\) 得：
\[\begin{aligned} &A\leq B\leq C\\ &g=\log(\prod_{i=1}^{A}\prod_{j=1}^{x}\prod_{k=1}^{y}\gcd(i,j)^{ijk})\\ &=\sum_{i=1}^{A}\sum_{j=1}^{x}\sum_{k=1}^{y}ijk\log(\gcd(i,j))\\ &=\sum_{k=1}^{y}k\sum_{i=1}^{A}\sum_{j=1}^{x}ij\log(\gcd(i,j))\\ &=W(y)\sum_{i=1}^{A}\sum_{j=1}^{x}ij\log(\gcd(i,j))\\ &=W(y)\sum_{p=1}^{A}\log(p)\sum_{i=1}^{A}\sum_{j=1}^{x}ij[\gcd(i,j)=p]\\ &=W(y)\sum_{p=1}^{A}\log(p)p^2\sum_{i=1}^{\lfloor\frac{A}{p}\rfloor}\sum_{j=1}^{\lfloor\frac{x}{p}\rfloor}ij[\gcd(i,j)=1]\\ &=W(y)\sum_{p=1}^{A}\log(p)p^2\sum_{i=1}^{\lfloor\frac{A}{p}\rfloor}\sum_{j=1}^{\lfloor\frac{x}{p}\rfloor}ij\sum_{d|i,d|j}\mu(d)\\ &=W(y)\sum_{p=1}^{A}\log(p)p^2\sum_{d=1}^{A}\mu(d)\sum_{i=1}^{\lfloor\frac{A}{dp}\rfloor}id\sum_{j=1}^{\lfloor\frac{x}{dp}\rfloor}jd\\ &=W(y)\sum_{p=1}^{A}\log(p)p^2\sum_{d=1}^{A}\mu(d)\sum_{i=1}^{\lfloor\frac{A}{dp}\rfloor}id\sum_{j=1}^{\lfloor\frac{x}{dp}\rfloor}jd\\ &=W(y)\sum_{p=1}^{A}\log(p)p^2\sum_{d=1}^{A}\mu(d)d^2W(\lfloor\frac{A}{dp}\rfloor)W(\lfloor\frac{x}{dp}\rfloor)\\ &=W(y)\sum_{T=1}^{A}W(\lfloor\frac{A}{T}\rfloor)W(\lfloor\frac{x}{T}\rfloor)\sum_{d|T}\mu(d)d^2\log(\frac{T}{d})(\frac{T}{d})^2\\ &=W(y)\sum_{T=1}^{A}T^2W(\lfloor\frac{A}{T}\rfloor)W(\lfloor\frac{x}{T}\rfloor)\sum_{d|T}\mu(d)\log(\frac{T}{d}) \end{aligned} \]取 \(G=\exp(g)\) 得：
\[G(x,y)=(\prod_{T=1}^{A}(\prod_{d|T}(\frac{T}{d})^{\mu(d)})^{T^2W(\lfloor\frac{A}{T}\rfloor)W(\lfloor\frac{x}{T}\rfloor)})^{W(y)} \]预处理 \(\prod_{d|T}(\frac{T}{d})^{\mu(d)})^{T^2}\) 即可。
type=2
\[\begin{aligned} &\prod_{i=1}^{A}\prod_{j=1}^{B}\prod_{k=1}^{C}\left(\frac{\text{lcm}(i,j)}{\gcd(i,k)}\right)^{\gcd(i,j,k)} \end{aligned} \]取 \(\log\) 得：
\[\begin{aligned} &\log(\prod_{i=1}^{A}\prod_{j=1}^{B}\prod_{k=1}^{C}\left(\frac{\text{lcm}(i,j)}{\gcd(i,k)}\right)^{\gcd(i,j,k)})\\ &=\sum_{i=1}^{A}\sum_{j=1}^{B}\sum_{k=1}^{C}\log(\text{lcm}(i,j))\gcd(i,j,k)-\log(\text{gcd}(i,k))\gcd(i,j,k)\\ &=\sum_{i=1}^{A}\sum_{j=1}^{B}\sum_{k=1}^{C}\left(\sum_{d|i,d|j,d|k}\varphi(d)\right)(\log(\text{lcm}(i,j))-\log(\gcd(i,k)))\\ &=\sum_{d=1}^{A}\varphi(d)\sum_{i=1}^{A}\sum_{j=1}^{B}\sum_{k=1}^{C}[d|A][d|B][d|C]\log(\text{lcm}(i,j))-\log(\gcd(i,k))\\ &=\sum_{d=1}^{A}\varphi(d)\sum_{i=1}^{\lfloor\frac{A}{d}\rfloor}\sum_{j=1}^{\lfloor\frac{B}{d}\rfloor}\sum_{k=1}^{\lfloor\frac{C}{d}\rfloor}\log(d\cdot\text{lcm}(i,j))-\log(d\cdot\gcd(i,k))\\ &=\sum_{d=1}^{A}\varphi(d)\sum_{i=1}^{\lfloor\frac{A}{d}\rfloor}\sum_{j=1}^{\lfloor\frac{B}{d}\rfloor}\sum_{k=1}^{\lfloor\frac{C}{d}\rfloor}\log(\text{lcm}(i,j))-\log(\gcd(i,k))\\ \end{aligned} \]取 \(\exp\) 得：
\[\prod_{d=1}^{A}\left(\prod_{i=1}^{\lfloor\frac{A}{d}\rfloor}\prod_{j=1}^{\lfloor\frac{B}{d}\rfloor}\prod_{k=1}^{\lfloor\frac{C}{d}\rfloor}\left(\frac{\text{lcm}(i,j)}{\gcd(i,k)}\right)\right)^{\varphi(d)} \]里面就是 type=0。数论分块套数论分块，做完了。
标签：P5518,lfloor,frac,log,sum,rfloor,MtOI2019,反演,prod From： https://www.cnblogs.com/zheyuanxie/p/p5518.html