莫比乌斯反演

Posted on 2020-07-30 Views:

莫比乌斯反演是OI中应对数论问题的一大杀器，可以把很多以前需要脑子想的问题无脑化，把很多脑子想不通的问题机械化，非常方便。

狄利克雷卷积

对于函数 f, g ，定义它们的狄利克雷卷积 $f \times g$ 为：

$(f \times g)(n) = \sum_{d \mid n} f(d)g\left(\frac{n}{d}\right)$

性质

积性

若 f, g 为积性函数，那么 $f \times g$ 继承它们的积性。

证明：令 n, m 为互素正整数，则易证的全体约数可以不重不漏地表示为 $\{d_nd_m \mid d_n \mid n, d_m \mid m\}$ 。

因此：

$\begin{aligned} (f \times g)(nm) &= \sum_{d | n} f(d)g\left(\frac{nm}{d}\right) \\ &= \sum_{d_n\mid n} \sum_{d_m \mid m} f(d_nd_m)g\left(\frac{nm}{d_nd_m}\right) \end{aligned}$

由

互素可知

互素以及 $\frac{n}{d_n}, \frac{m}{d_m}$ 互素，结合

的积性：

$\begin{aligned} \begin{aligned} (f \times g)(nm) &= \sum_{d_n\mid n} \sum_{d_m \mid m} f(d_n)f(d_m)g\left(\frac{n}{d_n}\right)g\left(\frac{m}{d_m}\right) \\ &= \sum_{d_n\mid n} f(d_n)g\left(\frac{n}{d_n}\right) \sum_{d_m \mid m} f(d_m)g\left(\frac{m}{d_m}\right) \\ &= (f \times g)(n) \cdot (f \times g)(m) \end{aligned} \end{aligned}$

证毕。

交换律

$f \times g = g \times f$

证明：由于约数是成对出现的，显然。

结合律

$(f \times g) \times h = f \times (g \times h)$

证明：我们需要稍微改变一下下标的写法，然后就非常清楚了：

$\begin{aligned} \left[(f \times g) \times h \right](n) &= \sum_{ab = n} (f \times g)(a) h(b) \\ &= \sum_{ab = n} \sum_{cd = a}f(c)g(d) h(b) \\ &= \sum_{bcd = n} f(c)g(d)h(b) \\ &= \sum_{ce = n} f(c) \sum_{bd = e} g(d)h(b) \\ &= \sum_{ce = n} f(c) (g \times h)(b) \\ &= \left[f \times (g \times h)\right](n) \end{aligned}$

得证。

单位元

定义

$\varepsilon(n) = [n = 1]$

易证 $\varepsilon$ 为狄利克雷卷积的单位元，也是一个积性函数，在之后的反演当中，我们也经常会把 $\varepsilon$ 作为艾弗森括号

的替代品，因为它具有更优良的性质，简单来说：

$[f(x) = y] = \varepsilon\left(\frac{f(x)}{y}\right)$

推论

关于狄利克雷卷积我们有两条非常重要的推论：

$\begin{aligned} \mu \times 1 &= \varepsilon \\ \varphi \times 1 &= I \end{aligned}$

当中

为值恒为

的常值函数，

为恒等函数，易证这两个都是完全积性函数。

证明：我们先证明第一条，假设 n > 1 有个素因子，从当中挑去若干个相乘组成的不含平方素因子的约数（如果约数含平方素因子则约数的 $\mu$ 为，可以直接忽略）则我们有：

$\begin{aligned} (\mu \times 1)(n) &= \sum_{i = 0}^r \binom{r}{i} (-1)^i \\ &= \sum_{i = 0}^r \binom{r}{i} (-1)^i\cdot 1^{r - i} \end{aligned}$

结合二项式定理，得到 $(\mu \times 1)(n) = (1-1)^r=0$ ，而如果

，手动展开得到 $(\mu \times 1)(1) = \mu(1) = 1$ 。两种情况结合起来得到 $\mu \times 1 = \varepsilon$ ，第一条推论得证。

对于第二条推论，我们将其展开：

$\sum_{d \mid n} \varphi(i) = n$

我们先考察

为素数（或其幂次）的情况，设

，则原式左边变为：

$\begin{aligned} \sum_{i = 0}^k \varphi(p^i) &= 1 +\sum_{i = 1} ^ k p^i\left(1 - {1 \over p}\right) \\ &= 1 + \left(1 - {1 \over p}\right)\sum_{i = 1} ^ k p^i \\ &= 1 + \frac{p - 1}{p} \cdot \frac{p^{k + 1} - p}{p - 1} \\ &= 1 + p^k - 1 \\ &= p^k \end{aligned}$

因此在

为素数或其幂次时推论得证，而我们知道 $\varphi \times 1$ 继承了积性，因此我们可以利用积性把推论推广到不为素数的情况（通过分解素因数即可），证毕。

莫比乌斯反演

定理： $f \times 1 = g$ 当且仅当 $f = g \times \mu$ 。

证明：本质上是狄利克雷卷积的推论的推论，先正着来一轮，两边同时乘以 $\mu$ ：

$\begin{aligned} f \times 1 &= g \\ \Rightarrow f \times 1 \times \mu &= g \times \mu \\ \Rightarrow f \times \varepsilon &= g \times \mu \\ \Rightarrow f &= g \times \mu \\ \end{aligned}$

我们再反着来一轮，两边同时乘上

：

$\begin{aligned} f &= g \times \mu \\ \Rightarrow f \times 1 &= g \times \mu \times 1 \\ \Rightarrow f \times 1 &= g \times \varepsilon \\ \Rightarrow f \times 1 &= g \end{aligned}$

（所以说不要迷行网上那种大力出奇迹几个 $\sum$ 展开来回套的证明，看这个多简单）

虽然存在这个莫比乌斯反演定理，但是我们更多的时候还是习惯逆用狄利克雷卷积的那两个推论。

示例： $\varphi(n)$

$\begin{aligned} \varphi(n) &= \sum_{i = 1}^n [\gcd(i, n) = 1] \\ &= \sum_{i = 1}^n \varepsilon(\gcd(i, n)) \\ \end{aligned}$

此时我们使用推论 $\varepsilon = \mu \times 1$ ：

$\begin{aligned} \varphi(n) &= \sum_{i = 1}^n \varepsilon(\gcd(i, n)) \\ &= \sum_{i = 1}^n \sum_{d \mid \gcd(i, n)} \mu(d) \\ &= \sum_{i = 1}^n \sum_{d \mid i, d \mid n} \mu(d) \\ \end{aligned}$

接下来我们把

的求和拖到前面去，本质上是从对约数求和变为对倍数算贡献：

$\begin{aligned} \varphi(n) &= \sum_{i = 1}^n \sum_{d \mid i, d \mid n} \mu(d) \\ &= \sum_{d \mid n} \mu(d) \sum_{i = 1, d \mid i}^n 1 \\ &= \sum_{d \mid n} \mu(d) \sum_{i = 1}^{n \over d} 1 \\ &= \sum_{d \mid n} \mu(d) \frac{n}{d} \\ &= \sum_{d \mid n} \mu(d) I\left(\frac{n}{d}\right) \\ &= (\mu \times id)(n) \end{aligned}$

因此我们证明了 $\varphi = \mu \times id$ ，虽然这个结论是可以直接从莫比乌斯反演定理推得的，但是呢，这个例子确实展示了莫比乌斯反演的很多常用套路：

把式子写下来
用或者 $\varepsilon$ 修饰
逆用狄利克雷卷积的推论，把求和式后面反演成卷积形式
通过算贡献的方式设法把的求和项连带着只和有关的函数值一起拖到最前面
化简后半部分

这一路下来其实是非常套路的，但往往效果拔群。

示例： $\sum_{i = 1}^n \varphi(i)$

以下为了方便起见，如果出现，皆假设 $n \le m$ ！

我们试试看刚刚学到的套路，来反演欧拉函数的前缀和：

$\begin{aligned} \sum_{i = 1}^n \varphi(i) &= \sum_{i = 1}^n \sum_{j = 1}^i [\gcd(i, j) = 1] \\ &= \sum_{i = 1}^n \sum_{j = 1}^i \varepsilon(\gcd(i, j) = 1) \\ &= \sum_{i = 1}^n \sum_{j = 1}^i \sum_{d \mid \gcd(i, j)} \mu(d) \\ &= \sum_{i = 1}^n \sum_{j = 1}^i \sum_{d \mid i, d \mid j} \mu(d) \\ &= \sum_{d = 1}^n \mu(d) \sum_{i = 1, d \mid i}^n \sum_{j = 1, d \mid j}^i 1\\ &= \sum_{d = 1}^n \mu(d) \sum_{i = 1}^{\left\lfloor \frac{n}{d} \right\rfloor} \sum_{j = 1}^i 1\\ &= \sum_{d = 1}^n \mu(d) \sum_{i = 1}^{\left\lfloor \frac{n}{d} \right\rfloor} i\\ &= \sum_{d = 1}^n \mu(d) \frac{\left\lfloor \frac{n}{d} \right\rfloor \left(\left\lfloor \frac{n}{d} \right\rfloor + 1\right)}{2}\\ &= \frac{1}{2} \sum_{d = 1}^n \mu(d) \left\lfloor \frac{n}{d} \right\rfloor \left(\left\lfloor \frac{n}{d} \right\rfloor + 1\right) \end{aligned}$

嗯，很好，很强大，但是这个有什么用呢？

示例： $\sum_{i = 1}^n \sum_{j = 1}^n [\gcd(i, j) = 1]$

这个式子对应POJ3090，即有一个 $n \times n$ 个格点，问从最左下角能够看到几个格点，我们发现如果格点 (i, j) 不互素的话，它一定不会被看到，因此题目就被转化成了我们要求的式子，常规做法是通过把格点劈成三角形，进行转化得到答案为 $2\sum_{i = 1}^n \varphi(n) - 1$ ，但是这毕竟还需要一点智商，而如果你莫比乌斯反演熟练的话，这个东西推起来是非常机械化的：

$\begin{aligned} \sum_{i = 1}^n \sum_{j = 1}^n [\gcd(i, j) = 1] &= \sum_{i = 1}^n \sum_{j = 1}^n \varepsilon(\gcd(i, j) = 1)\\ &= \sum_{i = 1}^n \sum_{j = 1}^n \sum_{d \mid i, d \mid j} \mu(d)\\ &= \sum_{d = 1}^n \mu(d) \sum_{i = 1, d \mid i}^n \sum_{j = 1, d \mid j}^n 1 \\ &= \sum_{d = 1}^n \mu(d) \sum_{i = 1}^{\left\lfloor \frac{n}{d} \right\rfloor} \sum_{j = 1}^{\left\lfloor \frac{n}{d} \right\rfloor} 1 \\ &= \sum_{d = 1}^n \mu(d) \left\lfloor \frac{n}{d} \right\rfloor^2 \\ &= 2 \left( \frac{1}{2} \sum_{d = 1}^n \mu(d) \left\lfloor \frac{n}{d} \right\rfloor \left(\left\lfloor \frac{n}{d} \right\rfloor + 1\right) \right) - \sum_{d = 1}^n \mu(d) \left\lfloor \frac{n}{d} \right\rfloor \\ &= 2\sum_{i = 1}^n \varphi(i) - \sum_{d = 1}^n \mu(d) \left\lfloor \frac{n}{d} \right\rfloor \end{aligned}$

那么 $\sum_{d = 1}^n \mu(d) \left\lfloor \frac{n}{d} \right\rfloor$ 又是什么呢？我们借着套路反着反演：

$\begin{aligned} \sum_{d = 1}^n \mu(d) \left\lfloor \frac{n}{d} \right\rfloor &= \sum_{d = 1}^n \mu(d) \sum_{i = 1, d \mid i}^n 1 \\ &= \sum_{i = 1}^n \sum_{d \mid i} \mu(d) \\ &= \sum_{i = 1}^n (\mu \times 1)(d) \\ &= \sum_{i = 1}^n \varepsilon(i) \\ &= 1 \end{aligned}$

原来这个是

啊，那么带回去我们就得到了：

$\sum_{i = 1}^n \sum_{j = 1}^n [\gcd(i, j) = 1] = 2\sum_{i = 1}^n \varphi(i) - 1$

以上推导中我们完全没有用到 $\varphi, \mu$ 的数学意义，而是顺着我们推导出的狄利克雷卷积的规则和推论进行着机械化的推导，最后也殊途同归，也许有些人会觉得这样没有卵用，那么试解：

$\sum_{i = 1}^n \sum_{j = 1}^m [\gcd(i, j) = 1]$

借助图形和数学意义的人看到这个式子大概就去世了，但是如果我们利用反演的话，类似以上的过程可以推得：

$\sum_{i = 1}^n \sum_{j = 1}^m [\gcd(i, j) = 1] = \sum_{d = 1}^n \mu(d) \left\lfloor \frac{n}{d} \right\rfloor \left\lfloor \frac{m}{d} \right\rfloor$