莫比乌斯反演学习笔记

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

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

莫比乌斯函数

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

$$\mu(i)= \begin{cases} 1&,i=1 \\ (-1)^k&,\forall a_k=1 \\ 0&,\exists a_k\gt1 \end{cases}$$

不妨写出$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$

莫比乌斯函数的性质

$$\sum_{d\mid n}\mu(d)= \begin{cases} 1 &,(n=1) \\ 0 &,(n\neq1) \end{cases}$$

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

$$\sum_{d\mid n}\mu(d)=\sum_{i=0}^k\binom{k}{i}(-1)^i1^{k-r}$$

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

求莫比乌斯函数

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

常用等式

$$\left\lfloor\frac{\lfloor\frac ab\rfloor}{c}\right\rfloor=\left\lfloor\frac{a}{bc}\right\rfloor$$

两个恒等式

$$\sum_{d\mid n}\mu(d)= \begin{cases} 1 &,(n=1) \\ 0 &,(n\neq1) \end{cases}$$ $$\sum_{k=0}^n(-1)^k\binom{n}{k}= \begin{cases} 0&,n\neq0 \\ 1&,n=0 \end{cases}$$

莫比乌斯反演

反演步骤

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)$

欧拉函数

$$\varphi(n)=\sum_{i=1}^n[\gcd(i,n)=1]=\sum_{i=1}^n\sum_{k\mid i,k\mid n}\mu(k)=\sum_{k\mid n}\mu(k)\lfloor\frac nk\rfloor$$

莫比乌斯反演的应用

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

$$\begin{aligned} \sum_{i=1}^n\sum_{j=1}^m\gcd(i,j)&=\sum_d d\sum_{i=1}^n\sum_{j=1}^m[\gcd(i,j)=d] \\ &=\sum_{d}d\sum_{i=1}^{\lfloor\frac nd\rfloor}\sum_{j=1}^{\lfloor\frac md\rfloor}[\gcd(i,j)=1] \\ &=\sum_{d}d\sum_{i=1}^{\lfloor\frac nd\rfloor}\sum_{j=1}^{\lfloor\frac md\rfloor}\sum_{k\mid i,k\mid j}\mu(k) \\ &=\sum_d d\sum_k\mu(k)\sum_{k\mid i}^{\lfloor\frac nd\rfloor}\sum_{k\mid j}^{\lfloor\frac md\rfloor} \\ &=\sum_{d}d\sum_k\mu(k)\lfloor\frac n{kd}\rfloor\lfloor\frac m{kd}\rfloor \end{aligned}$$

令$T=kd$，代入得：

$$\begin{aligned} &=\sum_{T}\lfloor\frac nT\rfloor\lfloor\frac mT\rfloor\sum_{k\mid T}\frac Tk\mu(k) \\ &=\sum_{T}\lfloor\frac nT\rfloor\lfloor\frac mT\rfloor\varphi(T) \end{aligned}$$

$\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莫比乌斯反演笔记手稿