莫比乌斯反演学习笔记 | Bill Yang's Blog
0%

莫比乌斯反演学习笔记

很早前就学过了,一直没整理学习笔记。
昨天我看机房里很多人都在写莫比乌斯反演,就心血来潮写一下。
本文主要讲讲莫比乌斯反演系列的零碎知识,果然莫比乌斯反演还是做题的好(牛奶还是武藏野的好)。

本文中,使用$[A]$代表$A$命题的$bool$表达,即$A$为真值为$1$,否则值为$0$。

莫比乌斯函数

$x$的莫比乌斯函数记为$\mu(x)$。
莫比乌斯函数主要用来形式化地表达在因数上的容斥关系。
为什么这么说呢,我们来看其定义:
若$i=p_1^{a_1}p_2^{a_2}\cdots p_k^{a_k}$。

不妨写出$16$以内的莫比乌斯函数。

$i$ $\mu(i)$ $i$ $\mu(i)$ $i$ $\mu(i)$ $i$ $\mu(i)$
$1$ $1$ $5$ $-1$ $9$ $0$ $13$ $-1$
$2$ $-1$ $6$ $1$ $10$ $1$ $14$ $1$
$3$ $-1$ $7$ $-1$ $11$ $-1$ $15$ $1$
$4$ $0$ $8$ $0$ $12$ $0$ $16$ $0$

莫比乌斯函数的性质

证明:
用二项式定理证明,设$n$有$k$种因子。

这就是莫比乌斯函数起到容斥的作用。
显然,这个性质可以用来判断$[n=1]$。

求莫比乌斯函数

我们可以利用线性筛来求莫比乌斯函数。
线性筛学习笔记

常用等式

两个恒等式

莫比乌斯反演

反演步骤

  1. 准备过程,列出$f$函数关于$g$函数的方程。即$f(n)=?g(n)$。
  2. 说废话(将$g(n)$转为$bool$表达式):$g(n)=\sum[i=?]g(i)$
  3. 利用恒等式代换。
  4. 交换$\sum$下标
  5. 利用$f(n)$进行代换

两类莫比乌斯反演

第一类莫比乌斯反演:
$f(n)=\sum_{d\mid n}g(d) \rightarrow g(n)=\sum_{d\mid n}\mu(d)f(\frac nd)$
第二类莫比乌斯反演:
$f(n)=\sum_{n\mid d}^Ng(d)\rightarrow g(n)=\sum_{n\mid d}^Nf(d)\mu(\frac dn)$

欧拉函数

莫比乌斯反演的应用

莫比乌斯反演常常用来解决快速计算$\gcd$问题。
举例:

令$T=kd$,代入得:

$\varphi$可以使用线性筛预处理处理,我们就可以枚举$T$求上式了,时间复杂度$O(n)$。
但如果我们加上多组数据$n,m$询问上式,时间复杂度就变成了$O(Tn)$。
有没有更高效的算法呢?

有!
我们发现$\lfloor\frac nT\rfloor$是不会轻易变化的,是过了连续的一段后才发生变化的,那么我们就可以计算出这一段的结束位置,对$\varphi$函数作个前缀和,就可以直接跳过这一段了。
这样的时间复杂度是$O(\sqrt n)$的。

技巧

有些时候我们化简出来的式子中含有比较复杂的项,我们将与$n$或$T$无关的项单独提取出来作为新函数,考虑如何预处理该函数。
数论中大部分函数都是积性函数,若不能使用$O(n\log n)$的方法预处理,就要考虑线性筛。
不妨打表找规律。

参考资料

  • 莫比乌斯反演.pptx - liuguangzhe
  • Bill_Yang莫比乌斯反演笔记手稿
姥爷们赏瓶冰阔落吧~