莫比乌斯反演

（以下除号皆表示整除）
对于一些式子复杂度大的数论题，或许用莫比乌斯反演可以高效解决问题。

前置技能：

• 基本数论函数

• 狄利克雷卷积

莫比乌斯函数满足 \(\mu \times I = \epsilon\)

即 \(\sum_{d|n}\mu(d) = [n = 1]\)

表达式为：

\[ n = 0 : \mu(n) = 1 \] \[ n = \prod_{p|n\,and\,p\,is\,prime} p : \mu(n)=(-1)^k \] \[ otherwise : \mu(n)=0 \]

证明：
暂时不会

莫比乌斯反演：
对于数论函数 \(f(n)\) ，设 \(F(n) = \sum_{d|n}f(d)\)
即 \(F = f \times I\)
则有 \(f(n) = \sum_{d|n}F(d)\cdot\mu(\frac{n}{d})\)
即 \(f = F \times \mu\)

证明：

\[ \because \; F = f\cdot I \] \[ \therefore \; F\cdot \mu = f\cdot I\cdot \mu \] \[ \because \; I\cdot \mu = \epsilon \] \[ \therefore \; F\cdot \mu = f\cdot \epsilon \] \[ \therefore \; f = F\cdot \mu \]

莫比乌斯反演好像主要是用来推式子，F 比 f 好做的话，就可以试试莫比乌斯反演。

另外事实上只需要熟知 \(\mu\) 函数的性质，直接推式子就行了，
绝大多数情况下（至少是我遇到的所有情况下）并不需要莫比乌斯反演。

另外莫比乌斯反演有个很简单的 \(O(nlogn)\) 实现，不需要筛 \(\mu\) ，直接按定义枚举每个数的倍数去筛即可。