Mobius

「莫比乌斯反演」学习笔记

关于莫比乌斯反演

莫比乌斯反演指的是 :

如果存在两个数论函数 \(F(x), f(x)\) 满足 \[ F(n) = \sum _ {d | n} f(d) \] 则有 \[ f(n) = \sum _ {d | n} \mu (d) F(\frac{n}{d}) \] 或者满足 \[ F(n) = \sum _ {n | d} f(d) \] 那么则有 \[ f(n) = \sum _ {n | d} \mu (\frac{d}{n}) F(d) \]

关于莫比乌斯函数

可能大家现在还不知 \(\mu (n)\) 是什么, 其实它就是一个容斥系数, 其定义为 \[ \mu(n) = \begin{cases} (-1)^{素数集合的大小} ~~~~~~~~~~ n可以被表示为若干个互异素数的乘积 \\ 0 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~otherwise \end{cases} \] 关于莫比乌斯函数, 它有一些很神奇的性质

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

  • \[ \sum_{d | n} \frac{\mu(d)}{d} = \frac{\varphi(n)}{n} \]

关于第一个式子的证明 :

\(n = 1\) 的时候, 很显然成立, 所以我们只用考虑 \(n > 1\) 的情况

由唯一分解定理可以知道 \(n = \prod _ i ^ k P_i ^ {a_i}\) 所以 \[ \sum_{d | n} \mu(d) = \sum _ {i = 0} ^ k \binom{k}{i} \cdot (-1) ^ i \] 由二项式定理可得 \[ \sum _ {i = 0} ^ k \binom{k}{i} (-1) ^ i \cdot 1 ^ {k - i} = (1 - 1) ^ k = 0 \] 证得.

关于第二个式子的证明

我们需要用到一些狄利克雷卷积相关的东西

我们知道 : \[ f * \epsilon = f \\ \mu * I = \epsilon\\ f * \mu * I = f \] 根据 \(\varphi\) 函数的性质, 我们知道 \[ \varphi * I = N \] 其实就是 \(n = \sum_{d | n} \varphi(d)\)

所以 \[ \varphi * I * \mu = N * \mu \to \varphi = N * \mu \] 展开一下 \[ \varphi (n) = \sum _ {d | n} \mu(d) \times N(\frac{n}{d}) \] 两边同时除以一个 \(n\)

可得 \[ \sum_{d | n} \frac{\mu(d)}{d} = \frac{\varphi(n)}{n} \] 由此证得.

关于莫比乌斯反演的证明

对于第一个式子 :

\(F(x)\) 的定义我们可以得到 \[ \sum _ {d | n} \mu (d) F(\frac{n}{d}) = \sum _ {d | n} \mu(d) \sum _ {d' | \frac{n}{d}} f(d') \] 然后我们知道集合 \(S_1 = \{d_i , d_i | n\}\)\(S_2 = \{\frac{n}{d_i}, d_i | n\}\) 是等价的

所以上面那个式子可以被表示为 \[ \sum _ {d \in S_1, d' \in S_2} \mu(d)f(d') \] 然后我们就可以交换一下求和的顺序了 \[ \sum _ {d | n} \mu(d) \sum _ {d' | \frac{n}{d}} f(d') = \sum _ {d' | n} f(d') \sum _ {d | \frac{n}{d'}} \mu(d) \] 结合莫比乌斯函数的第一个性质, 只有在 \(d' = n\)\(\sum _ {d | \frac{n}{d'}}\) 才不等于 \(0\), 其余都等于 \(0\)

证得.

对于第二个式子

并不会证

例题BZOJ1011 ZAP

给定 \(a, b, d\) , 求 \[ \sum _ {x \in [1, a], y \in [1, b]} [gcd(x, y) = d] \] 我们不妨设 \[ f(d) = \sum _ {x \in [1, a], y \in [1, b]} [gcd(x, y) = d] \\ F(d) = \sum _ {x \in [1, a], y \in [1, b]} [d \ \ | \ \ gcd(x, y)] \] 所以 \[ F(n) = \sum _ {n | d} f(d) \to f(n) = \sum _ {n | d} \mu (\frac{d}{n}) F(d) \] 并且 \[ F(d) = \lfloor \frac{a}{d} \rfloor \lfloor \frac{b}{d} \rfloor \] 这样的话, 对于一组 \((n, m, d)\) 求解的复杂度是 \(O(\frac{n}{d})\)

但是由于有多组询问, 我们这样会 \(T\)

我们考虑变换一下式子 \[ f(n) = \sum _ {i} \mu(i) F(i \times n) \] 然后我们需要用到用一个叫整除分块的东西, 可以在 \(O(\sqrt n)\) 的复杂度内求出 \[ \sum _ {i = 1} ^ n \lfloor\frac{n}{i}\rfloor \] 其实就是当 \(i\) 比较大时 $ $ 的值都相同, 我们可以合并在一起来算

可以证明 \(\lfloor\frac{n}{i}\rfloor\)\(i \in [1, n]\) 上只有 \(\sqrt {n}\) 种取值

对于两个乘在一起的情况也是类似的

所以我们按照上面变形完后的式子维护一个 \(\mu\) 的前缀和, 把值相同的 $F(x) $ 丢到一起算就好了

复杂度为 \(O(n + T \sqrt{n})\)