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

\[\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}\]

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

\[\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} \]

\[\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} \]

\[\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} \]

\[\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} \]

\[\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(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)} \]

\[\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} \]

\[\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} \]

\[\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)} \]