[MtOI2019]幽灵乐团 / 莫比乌斯反演基础练习题
题目描述
东风谷 早苗(Kochiya Sanae)非常喜欢幽灵乐团的演奏，她想对她们的演奏评分。
因为幽灵乐团有 \(3\) 个人，所以我们可以用 \(3\) 个正整数 \(A,B,C\) 来表示出乐团演奏的分数，她们的演奏分数可以表示为
\[\prod_{i=1}^{A}\prod_{j=1}^{B}\prod_{k=1}^{C}\left(\frac{\text{lcm}(i,j)}{\gcd(i,k)}\right)^{f(type)}
\]
因为音乐在不同的部分会有不同的听觉感受，所以 \(type\) 会在 \(\{0,1,2\}\) 中发生变化，其中：
\[\begin{aligned}
f(0)&=1 \cr
f(1)&=i \times j \times k \cr
f(2)&=\gcd(i,j,k)
\end{aligned}\]
因为乐团的歌实在太好听了，导致分数特别高，所以她们的分数要对给定的正整数 \(p\) 取模。
因为有很多歌曲要演奏，所以早苗给出了 \(T\) 组询问。
对于 \(100\%\) 的数据：
\[1\leq A,B,C\leq 10^5 \ \ \ \ 10^7 \leq p \leq 1.05\times 10^9\ \ \ \ p\in \{ prime\} \ \ \ \ T =70
\]
思路点拨
主要还是根据我的 莫反套路 来进行推导。
先看到原式，这个式子可以使用 \(lcm(i,j)=\dfrac{ij}{gcd(i,j)}\) 。
\[\prod_{i=1}^{A}\prod_{j=1}^{B}\prod_{k=1}^{C}\left(\frac{\text{lcm}(i,j)}{\gcd(i,k)}\right)^{f(type)}=\prod_{i=1}^{A}\prod_{j=1}^{B}\prod_{k=1}^{C}\left(\frac{ij}{\gcd(i,j)\gcd(i,k)}\right)^{f(type)}
\]
因为是模意义下的乘法，所以我们分子分母可以简答合并一下，那么就是：
\[\dfrac{\prod_{i=1}^A \prod_{j=1}^B \prod_{k=1}^C (ij)^f}{\prod_{i=1}^A \prod_{j=1}^B \prod_{k=1}^C \gcd(i,j)\gcd(i,k)^{f}}
\]
至此操作很常规，和一道叫 product 的莫反题一样。
然后我们考虑分子和分母，这又可以拆分：
\[\prod_{i=1}^A \prod_{j=1}^B \prod_{k=1}^C (ij)^f=\prod_{i=1}^A \prod_{j=1}^B \prod_{k=1}^C i^f\prod_{i=1}^A \prod_{j=1}^B \prod_{k=1}^C j^f
\]
这都差不多，一下只讲解左边一半 \(\prod_{i=1}^A \prod_{j=1}^B \prod_{k=1}^C i^f\)
分母差不多，也只讲解左边一半，右边是一样的。
\[\prod_{i=1}^A \prod_{j=1}^B \prod_{k=1}^C \gcd(i,j)^f
\]
\(type\) 三种，没有什么太大关联，所以分开讲解了。
\(type=0\)
此时 \(f=1\) 。十分的人性化，但是分数很少。
先讲最简单的分子(还是再讲一遍，我们分子分母都只讲一半，另一半是一样的)：
\[=\prod_{i=1}^A i^{BC}
\]
$O(n) $ 阶乘快速幂直接过。分母也很简单：
\[=\prod_{i=1}^A \prod_{j=1}^B \prod_{k=1}^C \gcd(i,j)
\]
和 \(k\) 没有什么太大关系啊，我们算 \(\prod_{i=1}^A \prod_{j=1}^B\gcd(i,j)\) ,带上 \(C\) 的幂就可以了。
看到这种式子，我们也是使用技巧（可以看一下上面的博客，广告）：枚举 \(\gcd\) ，然后式子就可以转化：
\[\prod_{d=1}^{A}d^{\sum_{i=1}^A \sum_{j=1}^B [\gcd(i,j)=d]}
\]
先考虑一下幂：
\[\sum_{i=1}^A\sum_{j=1}^B[\gcd(i,j)=d]=\sum_{i=1}^{\lfloor \frac{A}{d} \rfloor}\sum_{j=1}^{\lfloor \frac{B}{d} \rfloor} [\gcd(i,j)=1]
\]
现在我们可以莫反：
\[\sum_{i=1}^{\lfloor \frac{A}{d} \rfloor}\sum_{j=1}^{\lfloor \frac{B}{d} \rfloor} \sum_{k=1}^i \mu(k)[k|i][k|j]
\]
我们进而枚举 \(k\) ：
\[\sum_{k=1}^{\lfloor \frac{A}{d}\rfloor} \mu(k) \lfloor \dfrac{A}{kd}\rfloor \lfloor \dfrac{B}{kd} \rfloor
\]
我们集合 \(kd\) ，直接释放奥义 \(T=kd\) ，带回原式枚举 \(T\)
\[\prod_{d=1}^{A}d^{\sum_{k=1}^{\lfloor \frac{A}{d}\rfloor} \mu(k) \lfloor \frac{A}{kd}\rfloor \lfloor \frac{B}{kd} \rfloor}=\prod_{T=1}^{A} (\prod_{d|T}d^{\mu(\frac{T}{d})})^{\lfloor \frac{A}{T}\rfloor \lfloor \frac{B}{T}\rfloor}
\]
而中间括号内的部分 \(O(n \log n)\) 预处理一下。时间复杂度 \(O(T(\sqrt A \log AB+n \log n))\) 。大抵是可以过的罢。
这部分推出来是很基础的。