莫比乌斯反演学习笔记

发表于 更新于 分类于 ， 阅读次数： Disqus：

莫比乌斯函数

了解莫比乌斯反演前，我们先要了解莫比乌斯函数。记 \(\mu(n)\) 为莫比乌斯函数，\(n\) 可被分解质因数为 \(n = \prod_{i = 1}^{m}{ {p_i}^{c_i} }\) 定义如下：

\[ \mu(n) = \begin{cases} 1 & n = 1 \\ 0 & \exists i \in [1, m], c_i > 1 \\ (-1)^m & \forall i \in [1, m], c_i = 1 \\ \end{cases} \]

形式化地解释一下：

  • 当 \(n = 1\) 时，\(\mu(n) = 1\)；
  • 当 \(n\) 存在至少一个出现次数大于等于两次的质因子时，\(\mu(n) = 0\)；
  • 当 \(n\) 的所有质因子仅出现过一次，且 \(n\) 有奇数个质因子时，\(\mu(n) = -1\)；
  • 当 \(n\) 的所有质因子仅出现过一次，且 \(n\) 有偶数个质因子时，\(\mu(n) = 1\)。

莫比乌斯函数的性质

积性函数

首先易得 \(\mu(i)\) 为积性函数，即对于 \(\forall a, b \in \mathbb{N}^*\)，且 \(\gcd(a, b) = 1\)，均满足 \(\mu(ab) = \mu(a) \mu(b)\)。于是 \(\mu(n)\) 满足积性函数性质：

  • 令 \(n\) 分解质因数为 \(n = \prod_{i = 1}^{m}{ {p_i}^{c_i} }\)，则有 \(\mu(n) = \prod_{i = 1}^{m}{\mu({p_i}^{c_i})}\)

证明显然。

筛法

由于是积性函数，我们可以用线性筛求莫比乌斯函数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
bool isNotPrime[MAXN + 1];
int mu[MAXN + 1], primes[MAXN + 1], cnt;
inline void getPrimes() {
    isNotPrime[0] = isNotPrime[1] = true;
    mu[1] = 1;
    for (int i = 2; i <= MAXN; i++) {
        if (!isNotPrime[i]) {
            primes[++cnt] = i;
            mu[i] = -1;
        }

        for (int j = 1; j <= cnt; j++) {
            int t = i * primes[j];
            if (t > MAXN) break;

            isNotPrime[t] = true;

            if (i % primes[j] == 0) {
                mu[t] = 0;
                break;
            } else mu[t] = -mu[i];
        }
    }
}

特殊性质

莫比乌斯函数还有以下性质：

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

其中 \([n = 1]\) 表示：当 \(n = 1\) 时，该值为 \(1\)；否则该值为 \(0\)。

证明：

  • 当 \(n = 1\) 时，显然成立；
  • 当 \(n \ne 1\) 时：首先我们将 \(n\) 分解质因数为 \(n = \prod_{i = 1}^{m}{ {p_i}^{c_i} } \quad m > 1\)，设 \(n' = \prod_{i = 1}^{m}{p_i}\)，显然有 \(\sum_{d | n}{\mu(d)} = \sum_{d | n'}{\mu(d)}\)，通过组合数学可得：\(\sum_{d | n'}{\mu(d)} = \sum_{i = 0}^m{ {m \choose i} (-1)^m }\)。由二项式定理可得：\((1 + (-1))^m = \sum_{i = 0}^{m}{ {m \choose i} (-1)^m }\)，故我们可得 \(\sum_{d | n}{ \mu(d) } = 0^m = 0\)。

莫比乌斯反演

接下来就是莫比乌斯反演了。莫比乌斯反演定义如下：

设 \(f(n)\)，\(F(n)\) 为数论函数（即定义域为正整数的函数），则满足下列关系：

\[ F(n) = \sum_{d | n}{f(d)} \Rightarrow f(n) = \sum_{d | n}{\mu(d)F(\frac{n}{d})} \]

莫比乌斯反演还有下列另一种形式：

\[ F(n) = \sum_{n | d}{f(d)} \Rightarrow f(n) = \sum_{n | d}{\mu(\frac{d}{n})F(d)} \]

证明

狄利克雷卷积

在证明之前，我们需要先了解狄利克雷卷积。

对于两个数论函数 \(f(n)\) 与 \(g(n)\)，定义两函数的狄利克雷卷积（其中 \((n)\) 可省略不写）：

\[ (f * g)(n) = \sum_{d | n}{f(d)g(\frac{n}{d})} \]

显然该运算满足以下运算律：

  • 交换律：\(f * g = g * f\)
  • 结合律：\((f * g) * h = f * (g * h)\)
  • 分配律：\(f * (g + h) = f * g + f * h\)

我们定义 \(\varepsilon(n) = [n = 1]\) 为单位函数，显然有以下结论：

\[ f = f * \varepsilon = \varepsilon * f \]

证明步骤

接下来就可以证明了。利用卷积定义可推出：

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

\[ F(n) = \sum_{d | n}{f(d)} \Rightarrow F = f * 1 \]

故我们可以推出：

\[ \begin{align*} F * \mu &= f * 1 * \mu \\ \Rightarrow F * \mu &= f * (\mu * 1) \\ \Rightarrow F * \mu &= f * \varepsilon \\ \Rightarrow F * \mu &= f \end{align*} \]

将最后的等式展开即可得：

\[ f(n) = \sum_{d | n}{\mu(d)F(\frac{n}{d})} \]