莫比乌斯反演

莫比乌斯反演（Möbius inversion）是一种在数论中非常重要的工具，用于将一些累积求和公式反转。它通常用于处理数值序列的转换，尤其是在处理数学函数的和式时。简而言之，莫比乌斯反演允许我们通过已知的累积（或前缀和）公式，恢复原始的序列。

概念

假设我们有一个数列 $f(n)$ 和 $g(n)$，它们之间通过以下关系关联：

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

其中，$d|n$ 表示 $d$ 是 $n$ 的约数，求和是对所有 $n$ 的约数进行的。

莫比乌斯反演的核心思想就是通过已知的 $g(n)$，反推出原始的 $f(n)$：

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

这里的 $\mu(d)$ 是莫比乌斯函数，它的定义如下：

• $\mu(1) = 1$
• 如果 $d$ 是一个没有重复质因数的正整数，且 $d$ 的质因数个数为奇数，则 $\mu(d) = -1$
• 如果 $d$ 是一个包含重复质因数的正整数，则 $\mu(d) = 0$

莫比乌斯反演公式在许多数学问题中都有广泛应用，特别是在数论、组合数学和离散数学中。

例子

假设我们知道以下关系：

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

我们想从 $g(n)$ 推导出 $f(n)$，使用莫比乌斯反演公式：

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

假设 $g(n)$ 已知，莫比乌斯反演可以帮助我们恢复原始的 $f(n)$。

直观理解

可以把莫比乌斯反演看作是“反向求和”的过程。我们通过对约数的反转关系，利用莫比乌斯函数的特性，去除掉多余的部分，恢复原始的数列。

莫比乌斯函数

$$\mu(n) = \begin{cases} 1 & n = 1 \\\ 0 & n\text{含有平方因子} \\\ (-1)^k & k\text{为}n\text{的本质不同质因子个数} \end{cases} $$

莫反证明中要用到的莫比乌斯函数重要性质：

$$\sum_{d|n} \mu(d) = \begin{cases} 1 & n = 1 \\\ 0 & n\ne 1 \end{cases} $$

简单证明：

设 $n=\prod\limits_{i=1}^kp_i^{c_i}, n’=\prod\limits_{i=1}^kp_i$

则 $\sum\limits_{d|n}\mu(d) = \sum\limits_{d|n’}\mu(d) = \sum\limits_{i=0}^k C_k^i \cdot (-1)^i = (1 + (-1))^k$ （组合数学：k个质因子的选法 + 二项式定理）

故该式子当且仅当 $n=1$ 时，$\sum\limits_{d|1} \mu(d) = \mu(1) = 1$；否则为 $0$

引理1

$$\forall a,b,c\in Z，有 \bigg\lfloor \frac{a}{bc} \bigg\rfloor = \bigg\lfloor \frac{\lfloor \frac{a}{b} \rfloor}{c} \bigg\rfloor $$

简单证明：

$$\frac{a}{b} = \bigg\lfloor\frac{a}{b}\bigg\rfloor + r\quad(0\le r\lt1)\\\ \bigg\lfloor\frac{a}{bc}\bigg\rfloor = \bigg\lfloor\frac{a}{b} \cdot \frac{1}{c} \bigg\rfloor = \bigg\lfloor \frac{\Big(\lfloor \frac{a}{b} \rfloor + r\Big)}{c} \bigg\rfloor = \bigg\lfloor \frac{\lfloor \frac{a}{b} \rfloor}{c} + \frac{r}{c} \bigg\rfloor = \bigg\lfloor \frac{\lfloor \frac{a}{b} \rfloor}{c} \bigg\rfloor $$

引理2

$$\forall n\in N_+，则 \bigg|\left\{\lfloor{\frac{n}{d}}\rfloor ~|~ d\in N_+,d \le n \right\} \bigg| \le \lfloor{2\sqrt{n}}\rfloor $$

简单证明：

对于所有的 $d\le\lfloor{\sqrt{n}}\rfloor$，$\lfloor{\frac{n}{d}}\rfloor$ 至多有 $\lfloor\sqrt{n}\rfloor$ 种取值

对于所有的 $d\gt\lfloor{\sqrt{n}}\rfloor$，则 $\lfloor{\frac{n}{d}}\rfloor$，至多有 $\lfloor\sqrt{n}\rfloor$ 种取值

故加起来至多有 $\lfloor2\sqrt{n}\rfloor$ 种取值

数论分块

考虑含有 $\lfloor{\frac{n}{i}}\rfloor$ 的求和式子（$n$ 为常数），对于任意 $i(i\le n)$，找出一个最大的 $j$，$s.t. \lfloor{\frac{n}{i}}\rfloor = \lfloor{\frac{n}{j}}\rfloor$

此时 $j = \Big\lfloor{\dfrac{n}{\lfloor{\frac{n}{i}}\rfloor}}\Big\rfloor$

简单证明：

$$\begin{align} \lfloor{\frac{n}{i}}\rfloor &\le \frac{n}{i} \\\ {\frac{n}{\lfloor{\frac{n}{i}}\rfloor}} &\ge \frac{n}{\frac{n}{i}} \\\ \bigg\lfloor{\frac{n}{\lfloor{\frac{n}{i}}\rfloor}}\bigg\rfloor &\ge \bigg\lfloor\frac{n}{\frac{n}{i}}\bigg\rfloor = \lfloor{i}\rfloor = i \\\ j = \bigg\lfloor{\frac{n}{\lfloor{\frac{n}{i}}\rfloor}}\bigg\rfloor &\ge i \end{align} $$

已经证明了 $i \le j \le n$，故证明命题现还需证明: 当 $\lfloor{\frac{n}{i}}\rfloor = \lfloor{\frac{n}{j}}\rfloor$ 时，$j_{max}=\lfloor{\frac{n}{\lfloor{\frac{n}{i}}\rfloor}}\rfloor$

$$\begin{align} \lfloor{\frac{n}{i}}\rfloor &= \lfloor{\frac{n}{j}}\rfloor \\\ \lfloor{\frac{n}{i}}\rfloor &\le \frac{n}{j} \lt \lfloor{\frac{n}{i}}\rfloor + 1 \quad（常用不等式：\lfloor a \rfloor \le a \lt \lfloor a \rfloor + 1）\\\ \frac{1}{\lfloor{\frac{n}{i}}\rfloor} &\ge \frac{j}{n} \gt \frac{1}{\lfloor{\frac{n}{i}}\rfloor + 1} \quad（取倒数）\\\ \frac{n}{\lfloor{\frac{n}{i}}\rfloor + 1} &\lt j \le \frac{n}{\lfloor{\frac{n}{i}}\rfloor} \end{align} $$

故 $j_{max} = \bigg\lfloor{\dfrac{n}{\lfloor{\frac{n}{i}}\rfloor}}\bigg\rfloor$

证明过程

设 $f(n),g(n)$ 为两个数论函数

如果有 $F(n) = \sum\limits_{d|n}f(d)$，那么有 $f(n) = \sum\limits_{d|n}\mu(d)F(\dfrac{n}{d})$

如果有 $F(n) = \sum\limits_{n|d}f(d)$，那么有 $f(n) = \sum\limits_{n|d}\mu(\dfrac{d}{n})F(d)$

一式证明

$$\begin{align} \sum_{d|n}\mu(d)F(\frac{n}{d}) &= \sum_{d|n}\mu(d)\sum_{i~|\frac{n}{d}}f(i) \\\ &= \sum_{i|n} f(i) \sum_{d~|\frac{n}{i}}\mu(d) &\bigg(i~|\frac{n}{d} \Rightarrow id|n \Rightarrow d~| \frac{n}{i}\bigg)\\\ &= f(n) \end{align} $$

二式证明

$$\begin{align} \sum_{n|d}\mu(\frac{d}{n})F(d) &= \sum_{n|d}\mu(\frac{d}{n})\sum_{d|i}f(i) \\\ &= \sum_{n|i}f(i)\sum_{\frac{d}{n} | \frac{i}{n}} \mu(\frac{d}{n}) &\bigg(d | i \Rightarrow \frac{d}{n} | \frac{i}{n}\bigg) \\\ &= \sum_{n|i}f(i)\sum_{d’~| \frac{i}{n}} \mu(d’) \\\ &= f(n) \end{align} $$

可以类比 二重积分 在离散情况下 交换积分次序 的手段，会帮助理解
不过 二重积分 是在连续的情况下，因此画出 积分区域 穿个线就好了
而离散情况下，精准的找出每个点，就需要用 整除的性质 ，推推公式 了

容斥原理

容斥原理（Inclusion-Exclusion Principle）是一个用于计算多个集合的并集大小的数学公式。它的核心思想是，通过逐个添加集合的大小，再减去集合交集的大小，从而避免重复计数。容斥原理通常用于计算“至少一个条件成立”或“多个条件联合成立”的问题。

对于两个集合 $A$ 和 $B$，容斥原理的基本公式是：

$|A \cup B| = |A| + |B| - |A \cap B|$

对于三个集合 $A$, $B$, 和 $C$，容斥原理的扩展公式是：

$ |A \cup B \cup C| = |A| + |B| + |C| - |A \cap B| - |A \cap C| - |B \cap C| + |A \cap B \cap C| $

二者联系

在处理一些离散数学问题时，特别是在计算某些集合的计数或求和时，莫比乌斯反演可以看作是容斥原理的反向操作。通过莫比乌斯反演，我们可以从“总和”中去除掉那些重复的部分，从而恢复原始的数列或集合。

具体

1. 容斥原理的求和表示： 容斥原理通常用来计算多个条件下的“总数”，比如，给定一系列的集合，计算它们的并集大小。设 $A_i$ 是一系列集合，容斥原理可以表示为：

   $ |A_1 \cup A_2 \cup \cdots \cup A_k| = \sum_{i} |A_i| - \sum_{i<j} |A_i \cap A_j| + \sum_{i<j<k} |A_i \cap A_j \cap A_k| - \cdots + (-1)^{k+1} |A_1 \cap A_2 \cap \cdots \cap A_k| $

   这种求和方式其实是通过考虑各个集合的大小，并在重复计算时进行相应的加减操作，避免过多的重复计算。

2. 莫比乌斯反演的反向操作： 莫比乌斯反演就是在给定一个总和（比如容斥原理中的并集大小）后，通过利用莫比乌斯函数的加减法则，反向去除掉多重计数的部分，从而恢复到原始的数列或集合。

   具体来说，如果我们有一个关于集合的求和公式（比如容斥原理的表示），通过莫比乌斯反演可以得到一个反向求和的公式，恢复出每个单独集合的大小。例如，容斥原理通过计算并集的大小，往往会涉及到多个交集的计数，而莫比乌斯反演的作用就是通过加权的方式去除这些交集带来的多重计数。

公式

假设我们有 $f(n)$ 和 $g(n)$ 之间的关系，其中 $f(n)$ 是某些事件的计数，$g(n)$ 是这些事件的累积计数。容斥原理中，$g(n)$ 通常是通过对某些条件进行加减来计算的。如果我们知道 $g(n)$，那么使用莫比乌斯反演可以恢复原始的 $f(n)$。

公式为：

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

这里，$\mu(d)$ 是莫比乌斯函数，类似于容斥原理中的加减操作，它在“去重”时起到了重要作用。通过莫比乌斯反演，我们可以将累积的总和反转为单独的贡献。

例子

考虑一个数论问题，我们希望计算从1到 $n$ 中能够被某些数整除的整数个数。通过容斥原理，我们可以先计算每个数的倍数的个数，再通过减去交集的倍数个数来避免重复计数。而通过莫比乌斯反演，我们可以从这些累积的结果中“反向”恢复出每个数的贡献。

总结

• 容斥原理帮助我们计算多个集合的并集或交集的大小，通常涉及到逐层加减的操作。
• 莫比乌斯反演是容斥原理的“反向操作”，它允许我们从总和中去除重复的部分，恢复原始的数列或集合的贡献。
• 两者的核心思想相似，都是通过加减法则处理重叠部分，但莫比乌斯反演具有更为精妙的数学结构，使得它能够在数论和组合数学中广泛应用。

数论中的容斥

容斥原理可以帮助我们计算满足多个条件的整数个数。在数论中，这些条件通常是关于整数的“可除性”问题。具体来说，容斥原理通过以下步骤计算多个集合的交集和并集大小：

假设我们有一组集合 $A_1, A_2, \dots, A_k$，其中每个集合 $A_i$ 包含满足某个条件的整数（如能被某个数整除的整数）。容斥原理可以帮助我们计算这些集合的并集的大小，即满足至少一个条件的整数的个数。

回顾容斥

对于两个集合 $A$ 和 $B$，容斥原理的公式为：

$|A \cup B| = |A| + |B| - |A \cap B|$

对于三个集合 $A$, $B$, 和 $C$，容斥原理的扩展公式为：

$ |A \cup B \cup C| = |A| + |B| + |C| - |A \cap B| - |A \cap C| - |B \cap C| + |A \cap B \cap C| $

对于 $k$ 个集合 $A_1, A_2, \dots, A_k$，容斥原理的通用公式为：

$ |A_1 \cup A_2 \cup \dots \cup A_k| = \sum_{i} |A_i| - \sum_{i<j} |A_i \cap A_j| + \sum_{i<j<k} |A_i \cap A_j \cap A_k| - \cdots + (-1)^{k+1} |A_1 \cap A_2 \cap \dots \cap A_k| $

在数论中的应用

数论中的容斥原理主要用于计算满足某些整除条件的整数个数。比如：

1. 计算可被多个数整除的整数个数： 假设我们要计算从 1 到 $n$ 之间能被 $d_1, d_2, \dots, d_k$ 这些数之一整除的整数个数。可以定义每个集合 $A_i$ 为能被 $d_i$ 整除的整数集合。那么，我们就可以使用容斥原理来计算这些集合的并集大小，即符合至少一个条件的整数个数。

   $ |A\_1 \cup A\_2 \cup \dots \cup A\_k| = \sum\_{i=1}^{k} \left\lfloor \frac{n}{d\_i} \right\rfloor - \sum\_{1 \le i < j \le k} \left\lfloor \frac{n}{\text{lcm}(d\_i, d\_j)} \right\rfloor + \cdots + (-1)^{k+1} \left\lfloor \frac{n}{\text{lcm}(d\_1, d\_2, \dots, d\_k)} \right\rfloor $

   其中，$\left\lfloor \frac{n}{d\_i} \right\rfloor$ 表示从 1 到 $n$ 之间能被 $d_i$ 整除的整数个数，$\text{lcm}(d_1, d_2, \dots)$ 是最小公倍数。

2. 应用举例： 例如，计算 1 到 100 之间，能被 2 或 3 整除的整数个数。可以按照以下步骤使用容斥原理：

   • 计算能被 2 整除的数：$\left\lfloor \frac{100}{2} \right\rfloor = 50$
   • 计算能被 3 整除的数：$\left\lfloor \frac{100}{3} \right\rfloor = 33$
   • 计算能被 6（2 和 3 的最小公倍数）整除的数：$\left\lfloor \frac{100}{6} \right\rfloor = 16$

   于是，应用容斥原理得到的结果为：

   $50 + 33 - 16 = 67$

   所以，1 到 100 之间能被 2 或 3 整除的整数共有 67 个。

更一般的

容斥原理在更一般的数论问题中，尤其是涉及整除性、分解、以及多个条件下的整数计数时，都能起到很好的作用。通过使用容斥原理，我们可以精确计算出在某些条件下的整数个数，同时避免重复计算。

问题分析

给定两个数 $a$ 和 $b$，我们想求 $\gcd(a, b) = k$ 的数对个数，即从 $1$ 到 $n$ 之间选择两个数 $a$ 和 $b$，它们的最大公约数为 $k$。

思路：

1. 条件转化：

   • 首先，我们将所有的数对 $(a, b)$ 的最大公约数为 $k$ 的问题转化为：选择 $a = k \times x$ 和 $b = k \times y$，使得 $\gcd(x, y) = 1$，其中 $x$ 和 $y$ 是整数。
   • 也就是说，我们可以将原问题转化为：在 $1 \leq x, y \leq \frac{n}{k}$ 范围内，计算 $\gcd(x, y) = 1$ 的数对个数。

2. 数对个数计算：

   • 在 $1 \leq x, y \leq m$ 范围内，$m = \frac{n}{k}$，我们需要计算 $\gcd(x, y) = 1$ 的数对个数。
   • 如果直接计算所有数对的个数，总共有 $m^2$ 个数对。但是，这些数对中并不全是互质的，需要使用容斥原理来排除掉不是互质的数对。

3. 容斥原理的应用：

   • 假设 $\phi(m)$ 是欧拉函数，表示 $1 \leq x \leq m$ 中与 $x$ 互质的数的个数。我们可以通过容斥原理，依次排除所有包含公因数的数对。 具体步骤如下：
   • 计算总数对数：$m^2$
   • 然后通过容斥原理排除掉所有 $\gcd(x, y) \neq 1$ 的数对：
     • 对每个质数 $p$，排除所有 $x$ 和 $y$ 都能被 $p$ 整除的数对。即排除所有 $x, y$ 都在 $p$ 的倍数范围内。
     • 同理，对每对质数 $p_1, p_2$，排除所有 $x, y$ 能被 $p_1 \times p_2$ 整除的数对。

数学公式：

设 $m = \frac{n}{k}$，我们要求的数对个数为：

$ \text{数对个数} = m^2 - \sum_{p \mid m} \left( \left\lfloor \frac{m}{p} \right\rfloor^2 \right) + \sum_{p_1, p_2 \mid m} \left( \left\lfloor \frac{m}{p_1 p_2} \right\rfloor^2 \right) - \cdots $

其中，$ \sum\_{p \mid m} \left( \left\lfloor \frac{m}{p} \right\rfloor^2 \right) $ 表示排除所有能被质数 $p$ 整除的数对，类似地，其他项表示排除更高次的倍数条件。

具体步骤：

1. 计算 $m = \frac{n}{k}$。
2. 计算 $m^2$，这是所有数对的总数。
3. 对每个质数 $p$ 排除能够被 $p$ 整除的数对，即减去 $\left\lfloor \frac{m}{p} \right\rfloor^2$。
4. 对每对质数 $p_1, p_2$ 排除能够同时被 $p_1 \times p_2$ 整除的数对，加入 $\left\lfloor \frac{m}{p\_1 p\_2} \right\rfloor^2$，依此类推。
5. 最终的结果即为我们所求的最大公约数为 $k$ 的数对个数。

示例

假设 $n = 10$ 且 $k = 2$，那么：

• $m = \frac{10}{2} = 5$

• 所有数对的总数为 $m^2 = 5^2 = 25$

• 排除能被 2 整除的数对：$ \left\lfloor \frac{5}{2} \right\rfloor^2 = 2^2 = 4 $

• 没有更高次的倍数，最后的答案为：$25 - 4 = 21$。

所以，最大公约数为 2 的数对个数是 21。

容斥原理用于计算多个集合的并集或交集的大小，避免重复计数。

莫比乌斯反演是容斥原理的反向操作，利用莫比乌斯函数，通过加减法则恢复原始数列或集合。

在数论问题中，容斥原理和莫比乌斯反演常常结合使用，帮助我们精确计算符合多个条件的整数个数，避免重复计算。