qwe
\[\prod_{i=1}^A\prod_{j=1}^B\prod_{k=1}^C\bigg(\frac{\operatorname{lcm}(i,j)}{\gcd (i,k)}\bigg)^{f(type)}\]噔噔咚
\(\bold{type=0}\)
原式就是
\[\frac{\prod_{i=1}^A\prod_{j=1}^B\prod_{k=1}^Cij}{\bigg(\prod_{i=1}^A\prod_{j=1}^B\prod_{k=1}^C\gcd(i,j)\bigg)\bigg(\prod_{i=1}^A\prod_{j=1}^B\prod_{k=1}^C\gcd(i,k)\bigg)} \]上面的东西是
\[(A!)^{bc}(B!)^{ac} \]考虑算这个
\[\prod_{i=1}^A\prod_{j=1}^B\prod_{k=1}^C\gcd(i,j) \]因为分母上右边那个东西能变成
\[\prod_{i=1}^A\prod_{k=1}^C\prod_{j=1}^B\gcd(i,k) \]和这个东西是一样的
取 \(\ln\) 变成
\[\begin{aligned} &\sum_{i=1}^A\sum_{j=1}^B\sum_{k=1}^C\ln\gcd(i,j)\\ =&C\sum_{d=1}^{\min(A,B)}\ln d\sum_{i=1}^A\sum_{j=1}^B[\gcd(i,j)=d]\\ =&C\sum_{d=1}^{\min(A,B)}\ln d\sum_{i=1}^{\lfloor\frac{A}{d}\rfloor}\sum_{i=1}^{\lfloor\frac{B}{d}\rfloor}[\gcd(i,j)=1]\\ =&C\sum_{d=1}^{\min(A,B)}\ln d\sum_{i=1}^{\lfloor\frac{A}{d}\rfloor}\sum_{i=1}^{\lfloor\frac{B}{d}\rfloor}\sum_{x|i}\sum_{x|j}\mu(x)\\ =&C\sum_{d=1}^{\min(A,B)}\ln d\sum_{x=1}^{\lfloor\frac{A}{d}\rfloor}\lfloor\frac{A}{dx}\rfloor\lfloor\frac{B}{dx}\rfloor\mu(x) \end{aligned}\]令 \(s=dx\)
\[\begin{aligned} &=C\sum_{d=1}^{\min(A,B)}\sum_{x=1}^{\lfloor\frac{A}{d}\rfloor}\ln d\lfloor\frac{A}{s}\rfloor\lfloor\frac{B}{s}\rfloor\mu(x)\\ &=C\sum_{s=1}^{\min(A,B)}\sum_{x|s}\ln\frac{s}{x}\lfloor\frac{A}{s}\rfloor\lfloor\frac{B}{s}\rfloor\mu(x)\\ &=C\sum_{s=1}\lfloor\frac{A}{s}\rfloor\lfloor\frac{B}{s}\rfloor\sum_{x|s}\mu(x)\ln\frac{s}{x}\\ \end{aligned}\]然后再 \(\exp\) 回去就是
\[\begin{aligned} &\Bigg(e^{\sum_{s=1}\lfloor\frac{A}{s}\rfloor\lfloor\frac{B}{s}\rfloor\sum_{x|s}\mu(x)\ln\frac{s}{x}}\Bigg)^C\\ =&\Bigg(\prod_{s=1}^{\min(A,B)}\bigg(\prod_{x|s}\big(e^{\ln\frac{s}{x}}\big)^{\mu(x)}\bigg)^{\lfloor\frac{A}{s}\rfloor\lfloor\frac{B}{s}\rfloor}\Bigg)^C\\ =&\Bigg(\prod_{s=1}^{\min(A,B)}\bigg(\prod_{x|s}\big(\frac{s}{x}\big)^{\mu(x)}\bigg)^{\lfloor\frac{A}{s}\rfloor\lfloor\frac{B}{s}\rfloor}\Bigg)^C \end{aligned}\]令 \(F(s)=\prod_{x|s}\big(\frac{s}{x}\big)^{\mu(x)}\) 可以 \(O(n\log n)\) 预处理，然后就得到
\[\Bigg(\prod_{s=1}^{\min(A,B)}F(s)^{\lfloor\frac{A}{s}\rfloor\lfloor\frac{B}{s}\rfloor}\Bigg)^C \]整除分块可以 \(O(\sqrt{n}\log p)\) 做。
\(\bold{type=1}\)
原式是
\[\frac{\prod_{i=1}^A\prod_{j=1}^B\prod_{k=1}^C(ij)^{ijk}}{\bigg(\prod_{i=1}^A\prod_{j=1}^B\prod_{k=1}^C\gcd(i,j)^{ijk}\bigg)\bigg(\prod_{i=1}^A\prod_{j=1}^B\prod_{k=1}^C\gcd(i,k)^{ijk}\bigg)} \]算这个
\[\prod_{i=1}^A\prod_{j=1}^B\prod_{k=1}^C\gcd(i,j)^{ijk} \]取 \(\ln\)
\[\begin{aligned} &\sum_{i=1}^A\sum_{j=1}^B\sum_{k=1}^Cijk\ln\gcd(i,j)\\ =&\sum_{i=1}^A\sum_{j=1}^Bij\ln\gcd(i,j)\sum_{k=1}^Ck \end{aligned}\]令 \(S(n)=\frac{n(n+1)}{2}\)
\[\begin{aligned} =&S(C)\sum_{i=1}^A\sum_{j=1}^Bij\ln\gcd(i,j)\\ =&S(C)\sum_{d=1}^{\min(A,B)}\ln d\sum_{i=1}^A\sum_{j=1}^Bij[\gcd(i,j)=d]\\ =&S(C)\sum_{d=1}^{\min(A,B)}\ln d\sum_{i=1}^{\lfloor\frac{A}{d}\rfloor}\sum_{j=1}^{\lfloor\frac{B}{d}\rfloor}ijd^2[\gcd(i,j)=1]\\ =&S(C)\sum_{d=1}^{\min(A,B)}d^2\ln d\sum_{i=1}^{\lfloor\frac{A}{d}\rfloor}\sum_{j=1}^{\lfloor\frac{B}{d}\rfloor}ij\sum_{x|i}\sum_{x|j}\mu(x)\\ =&S(C)\sum_{d=1}^{\min(A,B)}d^2\ln d\sum_{x=1}^{\lfloor\frac{A}{d}\rfloor}\mu(x)\sum_{x|i,i\leq\lfloor\frac{A}{d}\rfloor}\sum_{x|j,j\leq\lfloor\frac{B}{d}\rfloor}ijx^2\\ =&S(C)\sum_{d=1}^{\min(A,B)}d^2\ln d\sum_{x=1}^{\lfloor\frac{A}{d}\rfloor}\mu(x)x^2S(\lfloor\frac{A}{dx}\rfloor)S(\lfloor\frac{B}{dx}\rfloor)\\ \end{aligned}\]令 \(G(n,m)=\sum_{x=1}^n\mu(x)x^2S(\lfloor\frac{n}{x}\rfloor)S(\lfloor\frac{m}{x}\rfloor)\)，可以预处理 \(\mu(x)x^2\) 前缀和之后 \(O(\sqrt{n})\) 算。
\[=S(C)\sum_{d=1}^{\min(A,B)}d^2\ln d\ G(\lfloor\frac{A}{d}\rfloor,\lfloor\frac{B}{d}\rfloor) \]取 \(\exp\)
\[\begin{aligned} &\Bigg(e^{\sum_{d=1}^{\min(A,B)}d^2\ln d\ G(\lfloor\frac{A}{d}\rfloor,\lfloor\frac{B}{d}\rfloor)}\Bigg)^{S(C)}\\ =&\Bigg(\prod_{d=1}^{\min(A,B)}\Big(d^{d^2}\Big)^{G(\lfloor\frac{A}{d}\rfloor,\lfloor\frac{B}{d}\rfloor)}\Bigg)^{S(C)}\\ \end{aligned}\]整除分块套整除分块，\(O(n\log p)\)。
标签：幽灵,lfloor,frac,ln,sum,rfloor,MtOI2019,乐团,prod From： https://www.cnblogs.com/yukari1735/p/16908442.html