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

标签：P5518 frac gcd luogu sum rfloor 反演 ij prod

重新学习了一下莫比乌斯反演，再来写一次这道题。

Part 1

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

\[=\prod_{i=1}^A\prod_{j=1}^B\prod_{k=1}^C\dfrac{ij}{\gcd(i,j)\gcd(i,k)} \]

分成两步求。每种相同的求法下面只列出一次。且钦定 \(\max(A,B)=A\)

\[\prod_{i=1}^A\prod_{j=1}^B\prod_{k=1}^Cij \]

\[\prod_{i=1}^A\prod_{j=1}^B\prod_{k=1}^Ci=\prod_{i=1}^A\prod_{j=1}^B i^C=\prod_{i=1}^Ai^{BC}=fac(A)^{BC} \]

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

\[=\prod_{i=1}^A\prod_{j=1}^B\gcd(i,j)^C \]

\[=(\prod_{d=1}^Ad^{\sum_{i=1}^A\sum_{j=1}^B[\gcd(i,j)=d]})^C \]

\[=(\prod_{d=1}^Ad^{\sum_{i=1}^{A/d}\sum_{j=1}^{B/d}[\gcd(i,j)=1]})^C \]

\[=(\prod_{d=1}^Ad^{\sum_{i=1}^{A/d}\sum_{j=1}^{B/d}\sum_{t|i}\sum_{t|j}\mu(t)})^C \]

\[=(\prod_{d=1}^Ad^{\sum_{t=1}^{A/d}\mu(t){\lfloor\frac{A}{td}\rfloor\lfloor\frac{B}{td}\rfloor}})^C \]

\[=(\prod_{T=1}^A(\prod_{d|T}d^{\mu(\frac{T}{d})})^{\lfloor\frac{A}{T}\rfloor\lfloor\frac{B}{T}\rfloor})^C \]

Part 2

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

\[=\prod_{i=1}^A\prod_{j=1}^B\prod_{k=1}^C(\dfrac{ij}{\gcd(i,j)\gcd(i,k)})^{ijk} \]

\[\prod_{i=1}^A\prod_{j=1}^B\prod_{k=1}^Ci^{ijk}=\prod_{i=1}^Ai^{i\times \sum_{j=1}^B j\sum_{k=1}^Ck}=(\prod_{i=1}^Ai^i)^{\frac{B(B+1)C(C+1)}{4}} \]

\[\prod_{i=1}^A\prod_{j=1}^B\prod_{k=1}^C\gcd(i,j)^{ijk} \]

\[=(\prod_{i=1}^A\prod_{j=1}^B\gcd(i,j)^{ij})^{\sum_{k=1}^Ck}=(\prod_{i=1}^A\prod_{j=1}^B\gcd(i,j)^{ij})^{\frac{C(C+1)}{2}} \]

标签：P5518,frac,gcd,luogu,sum,rfloor,反演,ij,prod
From： https://www.cnblogs.com/tidongCrazy/p/16739762.html