莫比乌斯函数的应用与莫比乌斯反演

毒瘤。

一些东西的证明放在最后的。

一些约定

高斯记号

对于命题 \text{A}，高斯记号

[\text{A}] =\begin{cases}1 & \text{if A is True} \\0 & \text{if A is False}\end{cases}

数论函数

对于定义域与值域均为 \mathbb{Z}^+ 的函数，称为数论函数。

莫比乌斯函数

将 x 质因数分解

x = \prod_{i = 1}^{\omega(x)} p_i^{k_i}

那么

\mu(x) =\begin{cases}1 & x = 1 \\0 & \exists k_i \geq 2 \\(-1)^{\omega(x)} &\text{otherwise}\\\end{cases}

重要结论

\sum_{d | n} \mu(d) = [n = 1] \tag{1.1}

证明见下

欧拉函数

\varphi(x) = \sum_{i = 1}^x [i \bot x]

重要结论

\sum_{d | n} \varphi(n) = n

自函数

id(x) = x

1 函数

1(x) = 1

单位元函数

e(x) = [x = 1]

这些函数都是积性的。

狄利克雷卷积

对于两个数论函数 f, g 他们的狄利克雷卷积

(f * g)(x) = \sum_{d | x} f(d) \times g(\dfrac{x}{d})

狄利克雷卷积在数论函数集上形成阿贝尔群。在积性数论函数集上形成群，且满足交换律，结合律。

把上面的两条重要性质用狄利克雷卷积来表示就是

1 * \mu = e \\1 * \varphi = id

数论分块

当 i 取遍 [1, n] 时，\Big\lfloor\dfrac{n}{i}\Big\rfloor 的值仅有 O(\sqrt{n}) 种。相同的值对应的 i 是连续的，我们称作一块。块的左端点如果为 l，右端点为

\Big\lfloor\dfrac{n}{\frac{n}{l}}\Big\rfloor \tag{1.2}

证明见下。

莫比乌斯函数的应用

套路一 交换和号

求

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

考虑莫比乌斯函数的性质

\sum_{d |n} \mu(d) = [n = 1]

我们把上式的 n 换做 \gcd(i, j)

\sum_{i = 1}^n \sum_{j = 1}^n \sum_{d | \gcd(i, j )} \mu(d)

一个重要的套路来了，因为 d | \gcd(i, j)，所以 d | i \land d | j，这是等价的。因此 i, j 都是 d 的倍数。所以我们枚举 i, j 是 d 的几倍。并且交换和号。（下文和号的上界省略下取整符号）。

\sum_{d = 1}^n \mu(d) \sum_{i = 1}^{\frac{n}{d}} \sum_{j = 1}^\frac{n}{d} 1 \\\sum_{d = 1}^n \mu(d) \times (\lfloor\frac{n}{d}\rfloor)^2

用线性筛筛出 \mu 并计算前缀和，再用数论分块即可 O(n) + O(\sqrt{n}) 解决问题。

---

再来看下一个式子

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

虽然考虑意义我们发现这个式子明显等于 n \times \dfrac{\varphi(n)}{2}，不过我们仍然可以套用莫比乌斯函数。

\begin{aligned}&= \sum_{i = 1}^n \sum_{j = 1}^n i \times j \sum_{d | \gcd(i, j)} \mu(d) \\&= \sum_{d = 1}^n \mu(d) \sum_{i = 1}^{\frac{n}{d}} \sum_{j = 1}^\frac{n}{d} i \times j \times d^2\ (\text{don't forget about the}\ d^2!) \\&= \sum_{d = 1}^{n} \mu(d) \times d^2 \times A^2\end{aligned}

其中 A = \dfrac{1}{2} \times \Big\lfloor\dfrac{n}{d}\Big\rfloor\times (\Big\lfloor\dfrac{n}{d}\Big\rfloor +1)。

套路二 枚举分数转换狄利克雷卷积

求

\sum_{i = 1}^n \sum_{j = 1}^n \operatorname{lcm}(i, j)

先化开来

\begin{aligned}&= \sum_{i = 1}^n \sum_{j = 1}^n \dfrac{i \times j}{\gcd(i, j)} \\&= \sum_{d = 1}^n \sum_{i = 1}^n \sum_{j = 1}^n \dfrac{i \times j}{d} \times [\gcd(i, j) = d] \\&= \sum_{d = 1}^n \sum_{i = 1}^\frac{n}{d} \sum_{j = 1}^\frac{n}{d} i \times j \times d \times[\gcd(i, j) = 1] \\&= \sum_{d = 1}^n d\sum_{x = 1}^{\frac{n}{d}} \mu(x) \times x^2 \sum_{i = 1}^\frac{n}{dx}\sum_{j = 1}^\frac{n}{dx} i \times j\end{aligned}

按之前的套路继续推下去发现只能单次 O(n \sqrt{n}) 的复杂度解决。这里有第二个套路。枚举 T = dx。

\begin{aligned}&= \sum_{T = 1}^n \sum_{d | T} d \times \mu(\dfrac{T}{d}) \times F(\Big\lfloor\dfrac{n}{T}\Big\rfloor)^2 \times (\dfrac{T}{d})^2\\ &= \sum_{T = 1}^n F(\Big\lfloor\dfrac{n}{T}\Big\rfloor)^2 \times \sum_{d | T} d \times \mu(\dfrac{T}{d}) \times (\dfrac{T}{d})^2 \\&= \sum_{T = 1}^n T \times F(\Big\lfloor\dfrac{n}{T}\Big\rfloor)^2 \times \sum_{d | T} \dfrac{T}{d} \times \mu(\dfrac{T}{d}) \\&= \sum_{T = 1}^n T \times F(\Big\lfloor\dfrac{n}{T}\Big\rfloor)^2 \times \sum_{d | T} d \times \mu(d)\end{aligned}

（F(n) 代表 \sum_{i = 1}^n）

如果我们记 h(T) = \sum_{d | T} d \times \mu(d)，会发现 h 是一个积性的函数（证明见下）。

晒出 h 来就能 O(n) + O(\sqrt{n}) 解决问题了。

莫比乌斯反演

如果式子满足：

f(n) = \sum_{d | n} g(d)

那么就有：

g(n) = \sum_{d | n} f(n) \times \mu(\dfrac{n}{d})

证明见下。

一些证明

1.1

式子等价于 1 * \mu = e。因为 1, \mu, e 这些函数都是积性的，所以只需要证明对于任意质数 p 与 k \in \mathbb{Z}^+，都有

e(p^k)=(1 * \mu)(p^k)

即可。

\begin{aligned}(1*\mu)(p^k) &= \sum_{d | p^k} 1 \times \mu(\dfrac{p^k}{d}) \\&= \sum_{d | p^k} \mu(d) \\\end{aligned}

因为 p 为质数，所以 d 一定可以表示为 p^i 的形式，且 i | k。

因为当 i \geq 2 时，对答案没有贡献。所以当 i = 1 时，贡献为 -1；i = 0 时，贡献为 1。

所以上述和式展开来写时类似

1 + (-1) + 0 + 0 \cdots + 0

的。

故当定义域为质数域质数组成的所有数（即 \mathbb{Z}^+ - \{1\}），有 1 * \mu = e。

然而我们发现，当 x = 1 时，上面的和式只会出现第一项，即 1 的那一项。所以 (1 * \mu)(1) = 1 = e(1)。

1.2

假设 i > j。

\because \Big\lfloor\dfrac{n}{i}\Big\rfloor = \Big\lfloor\dfrac{n}{j}\Big\rfloor \\\therefore \dfrac{n}{i} \geq \Big\lfloor\dfrac{n}{j}\Big\rfloor \\\therefore \dfrac{i}{n} \leq \Big\lfloor\dfrac{n}{j}\Big\rfloor^{-1} \\\therefore i \leq n \times \Big\lfloor\dfrac{n}{j}\Big\rfloor^{-1}

套路二的积性函数

对于 a \bot b，如果有

h(a \times b) = h(a) \times h(b)

那就是积性函数了。

展开来写：

\sum_{d |a \times b} d \times \mu(d) = \sum_{d_1 |a} \sum_{d_2 | b} d_1 \times d_2 \times \mu(d_1) \times \mu(d_2)

对于 a \times b 的因子 d，由于 a \bot b，一定可以唯一地表示成 \gcd(d, a) \times \gcd(d, b)，也就是说，左边的和号可以拆成唯一的两个数的乘积，而且这两个数一定可以在右边的和号中分别找到。

故成立。

莫比乌斯反演

考虑第一个式子：

f = 1 * g

第二个式子：

g = \mu * f

因为 \mu 是 1 的逆元（1 * \mu = e），所以乘上 1 的逆元就可以得到下面的式子了。