莫比乌斯函数很简单，莫比乌斯函数 \(\mu(n) = \begin{cases} 0 & n 有平方质因子 \\ 1 & n = 1 \\ (-1)^k&k 为本质不同质因子数量\end{cases}\)
莫比乌斯函数可以用来做容斥，具体怎么做等会儿说。
莫比乌斯函数有一些常用的性质
- \(\mu(n)\) 为积性函数。
显而易见。因而可以线性筛，筛法很弱智，不写了。 - \(\sum\limits_{d|n}\mu(d) = \begin{cases}1 & n = 1 \\ 0 & n \not = 1\end{cases}\)
来证明。\(n = 1\) 显然成立。这个很像狄利克雷卷积，但我们不用狄利克雷卷积做因为没必要（虚晃一枪 2333333）。我们设 \(n = p_1^{c_1}p_2^{c_2}\dots p_k^{c_k}\)，显而易见对于 \(n' = p_1p_2\dots p_k\) 会有同样的结果。我们讨论 \(n'\)。
对于 \(k\) 奇偶性分类讨论。若 \(k\) 为奇数，假设我们取了其中 \(a(a\le k)\) 个质因子，则 \(k - a\) 必然与 \(a\) 奇偶性不同，换言之 \(\mu(k - a) + \mu(a) = 0\)。若 \(k\) 为偶数，显而易见我们每次取奇数个质因子与偶数个质因子它们的方案数相同，因此其和也为 \(0\)。
额感性理解罢毕竟 SX 太菜了要理解他的语文与数学水平 qwq - \(\sum\limits_{d|n} \dfrac{\mu(d)}{d} = \dfrac{\varphi(n)}{n}\)
用莫比乌斯反演证，话说这个性质没啥常用可言吧。。。。
莫比乌斯反演其实很弱智。
若 \(f(n) = \sum\limits_{d|n} g(d)\) 则 \(g(n) = \sum\limits_{d|n} \mu(d)f(\dfrac{n}{d})\)。
这样看起来并不显然，因此并不好背诵（雾），设函数 \(o(n)\) 恒等于 \(1\)，用狄利克雷卷积形式写就是 \(g*o = f, f*\mu = g\)，这样就好背诵多了，事实上也好证明多了，但是我狄利克雷卷积没学好，所以不会用这个方法证，只能用愚蠢的方法证明了。如果有巨佬愿意教我用狄利克雷卷积方法整吗 QAQ QQ 2392303708 qwq
暴力拆原式 \(g(n) = \sum\limits_{d|n} \mu(d)\sum\limits_{d'|\frac{n}{d}}g(d') = \sum\limits_{d|n} g(d) \sum\limits_{d'|\frac{n}{d}} \mu(d')\)。
当 \(d = n\) 时，\(\frac{n}{d} = 1\)，根据上面的性质 1 有 \(\sum\limits_{d'|\frac{n}{d}} \mu(d') = 1\)，这次求和会累加一个 \(g(n)\)。若 \(d\not= n\)，\(\frac{n}{d} \not = 1\)，那么根据上面的性质则 \(\sum\limits_{d'|\frac{n}{d}} \mu(d') = 0\)。
则最后有 \(\sum\limits_{d|n} g(d) \sum\limits_{d'|\frac{n}{d}} \mu(d') = g(n)\)。
顺带一提某书压根没有说明上面这一步的原因，这是糟的。
证明 \(\sum\limits_{d|n} \dfrac{\mu(d)}{d} = \dfrac{\varphi(n)}{n}\)。同乘 \(n\) 则 \(\sum\limits_{d|n}\mu(d)\dfrac{n}{d} = \varphi(n)\)。令 \(f(n) = n\)，则 \(f(n) = n = \sum\limits_{d|n} \varphi(d)\)，根据莫比乌斯反演，则 \(\sum\limits_{d|n}\mu(d)f(\dfrac{n}{d}) = \varphi(n)\)，即 \(\sum\limits_{d|n}\mu(d)\dfrac{n}{d}= \varphi(n)\)，原命题得证。
标签：dfrac,limits,乌斯,sum,mu,反演,莫比 From： https://www.cnblogs.com/thirty-two/p/16640972.html