这是一份极其粗糙的莫比乌斯函数学习笔记

• 莫比乌斯反演非常巧妙玄学，它通过__卷积__，和式变换以及最关键的整数分块的有机结合降低了函数的复杂度。

莫比乌斯函数

• \(\mu(d)\) 的定义：

  1.当d=1时，\(\mu(d)=1\)；

  2.当d唯一分解后有一个质因数的次数大于1，那么\(\mu(d)=0\)

  3.否则，设n可以分解为n个不同的质数相乘，则\(\mu(d)=(-1)^{n}\)。

• 一些结论：

  1.\(\sum_{d|n}\mu(d)=[n==1]\),也就是说，n=1时函数值为1，否则为0。这个用二项式定理来证

  2.对于任意正整数n,\(\sum_{d|n}\frac{\mu(d)}{d}=\frac{\phi(n)}{n}\),证明以后补。

• 筛莫比乌斯函数可以用线性筛。

莫比乌斯反演

• 定理：

  \[ \begin{align*} &设f(n)=\sum_{d|n}g(d),\\ &则g(n)=\sum_{d|n}\mu(d)f(\lfloor \frac{n}{d}\rfloor)。 \end{align*} \]

• 证明：

  \[ \begin{align*} &\sum_{d|n}\mu(d)f(\lfloor \frac{n}{d}\rfloor)= \\ &\sum_{d|n}\mu(\lfloor \frac{n}{d}\rfloor)\sum_{i|d}f(i)= \\ &\sum_{i|n}f(i)\sum_{d|\lfloor \frac{n}{i}\rfloor}\mu(d)=f(n) \end{align*} \]

• 还有一种理解方式就是用狄利克雷卷积（用*表示）来理解莫比乌斯反演。下面直接给出几个定理：

  设：

  1.\(Id(n)=n\)

  2.\(\epsilon(n)=[n==1]\)

  3.\(I(n)=1\)

  4.\(\mu 和\phi 就不说了\)。

  结论：

  1.\(\mu *Id=\epsilon,这就是\sum_{d|n}\mu(d)=[n==1]\).

  2.\(\mu*Id=\phi\).这个定理可以用容斥来证明。反过来\(\mu*Id=\phi\Longrightarrow Id=\sum_{d|n}\phi(d)\)。用卷积可以证明这个常见的结论。

题目