初探莫比乌斯反演

ggc123 · 2026-08-23 16:33:36 · 算法·理论

更好的阅读体验？

引入

算术函数

在数论中，我们研究的对象是正整数，因此数论中关心的函数，定义域就变成了正整数集，那么这一类函数叫做算术函数。

例如下面的这个函数：

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

这个函数是欧拉函数，它代表的是小于等于 n 的正整数中，与 n 互质的数的个数。

积性函数

如果 \gcd(a,b) = 1，若函数 f(ab) = f(a)f(b)，则称 f 是积性函数。特别地，如果 \gcd(a,b) \ne 1，但仍有 f(ab) = f(a)f(b)，那么称 f 是完全积性函数。

注意到欧拉函数是积性的，但这非本文讨论范围，故不给出证明。

那为什么要关心这个性质呢？根据唯一分解定理，任意大于 1 的整数都可以唯一地表示成有限个质数的乘积，即

n = p_1^{\alpha_1}p_2^{\alpha_2}p_3^{\alpha_3}\cdots p_k^{\alpha_k}

如果一个函数是积性的，那么它所有地方的函数值都由质数幂次处的函数值决定。

和函数

对于算术函数 f(n)，定义

F(n) = \sum_{d \mid n} f(d)

即对所有正整数约数 d 的函数值 f(d) 求和，这个函数 F(n) 称作 f 的和函数。

例如：

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

即欧拉函数的和函数是恒等函数 n。

莫比乌斯反演的形式

对于给定的 n，F(n) 中包含哪些 f(d) 是确定的，因此可以通过解方程组从 F 反解出 f。

观察下列的几个等式：

\begin{align} F(1) &= f(1) \nonumber \\ F(2) &= f(1)+f(2) \nonumber \\ F(3) &= f(1)+f(3) \nonumber \\ F(4) &= f(1)+f(2)+f(4) \nonumber \\ F(5) &= f(1)+f(5)\nonumber \\ F(6) &= f(1)+f(2)+f(3)+f(6) \nonumber \end{align}

将 f(d) 看作未知数，F(n) 看作已知量，那么这里有 6 个方程 6 个未知数，可以解得每一个 f(d)：

\begin{align} f(1) &= F(1) \nonumber \\ f(2) &= F(2)-F(1) \nonumber \\ f(3) &= F(3)-F(1) \nonumber \\ f(4) &= F(4) - F(2) \nonumber \\ f(5) &= F(5) - F(1) \nonumber \\ f(6) &= F(6)-F(3)-F(2) + F(1)\nonumber \end{align}

现在发挥注意力，注意到右边 F 的“自变量”都是左边 f 的自变量的约数，并且前面的系数呈现出某种规律。把这些系数记作一个函数 \mu，于是可以形式地写成：

F(n) = \sum_{d \mid n} f(d) \Longleftrightarrow f(n) = \sum_{d \mid n} \mu(d)F\left(\frac{n}{d}\right) = (\mu*F)(n)

这个变形叫做莫比乌斯反演，这种形式就是狄利克雷卷积。这里的 \mu 是莫比乌斯函数，它是由反演公式唯一确定的。

莫比乌斯函数

形式

现在我们已经有了如下的变形：

F(n) = \sum_{d \mid n} f(d) \Longleftrightarrow f(n) = \sum_{d \mid n} \mu(d)F\left(\frac{n}{d}\right)

我们来推导莫比乌斯函数 \mu(n) 的取值。

当 n = 1 时

由 F(1)=f(1)，同时反演公式给出：
f(1) = \mu(1)F(1)
这里取一个 f(1)\neq 0 的算术函数，所以 \mu(1)=1。
当 n 为质数时

设 n=p，则 F(p)=f(p)+f(1)，所以 f(p)=F(p)-F(1)。

代入反演公式：
f(p)=\mu(1)F(p)+\mu(p)F(1)
即
F(p)-F(1)=F(p)+\mu(p)F(1)
所以 \mu(p)=-1。
当 n 为质数的幂时，记 n=p^k
- 当 k=2 时
  代入反演公式： $$ f(p^2)=\mu(1)F(p^2)+\mu(p)F(p)+\mu(p^2)F(1) $$ 即 $$ F(p^2)-F(p)=F(p^2)-F(p)+\mu(p^2)F(1) $$ 所以 $\mu(p^2)=0$。
- 当 k=3 时
  $$ f(p^3)=F(p^3)-F(p^2) $$ 代入反演公式： $$ f(p^3)=\mu(1)F(p^3)+\mu(p)F(p^2)+\mu(p^2)F(p)+\mu(p^3)F(1) $$ 因为 $\mu(1)=1,\mu(p)=-1,\mu(p^2)=0$，得到 $$ F(p^3)-F(p^2)=F(p^3)-F(p^2)+\mu(p^3)F(1) $$ 所以 $\mu(p^3)=0$。
同理，对任意 k\ge 2，可归纳得到 \mu(p^k)=0。
当 n 为合数时

为了处理合数，我们需要知道 \mu 的积性。事实上，\mu 是积性函数，即若 \gcd(a,b)=1，则
\mu(ab)=\mu(a)\mu(b)
证明：设 a 有平方因子（由于 a,b 对称，这里只讨论 a 有平方因子），则 ab 也有平方因子，两边均为 0；设 a,b 都无平方因子，且
a=p_1p_2\cdots p_r,\quad b=q_1q_2\cdots q_s
其中所有 p_i,q_j 互不相同。于是 ab 是 r+s 个不同素数之积，所以
\mu(ab)=(-1)^{r+s}=(-1)^r(-1)^s=\mu(a)\mu(b)
故 \mu 是积性函数。

现在由唯一分解定理：
n = p_1^{\alpha_1}p_2^{\alpha_2}p_3^{\alpha_3}\cdots p_k^{\alpha_k}
根据积性：
\mu(n) = \mu(p_1^{\alpha_1})\mu(p_2^{\alpha_2}) \cdots \mu(p_k^{\alpha_k})
- 若存在 i 使得 \alpha_i\ge 2，则 \mu(p_i^{\alpha_i})=0，于是 \mu(n)=0；
- 若所有 \alpha_i=1，则每一项都是 -1，共 k 个，所以 \mu(n)=(-1)^k。

总结一下，莫比乌斯函数的取值：

\mu(n)= \begin{cases} 1 & n=1\\ 0 & \exists d>1,\,d^2\mid n \\ (-1)^{\omega(n)} & \text{otherwise} \end{cases}

其中，\omega(n) 表示 n 的不同质因子个数。

求法

如果我们只关心单个 n 的 \mu(n)，可以先将其质因数分解，再根据上面的式子求值，这样的时间复杂度是 O(\sqrt{n})。

int mu(int x) {
    if (x == 1)    return 1;// 第一种情况
    int cnt = 0;//这个即为 ω(n)
    for (int i = 2; i * i <= x; i++) {
        if (x % i == 0) {
            cnt++, x /= i;
            if (x % i == 0)    return 0; // 第二种情况，即 n 是质数幂的倍数
        }
    }
    if (x > 1) cnt++; // 处理剩余的大于 1 的质因子
    return (cnt & 1 ? -1 : 1);//第三种情况
}

如果我们想求 1 到 n 的 \mu 值，可以使用线性筛求得。

const int MAXN = 1e7+5;
int tot = 0;
int p[MAXN], mu[MAXN];
bool vis[MAXN];

void get(int n) {
    mu[1] = 1;
    for (int i = 2; i <= n; i++) {
        if (!vis[i])    p[++tot] = i, mu[i] = -1;
        for (int j = 1; j <= tot && i * p[j] <= n; j++) {
            vis[i*p[j]] = 1;
            if (i % p[j] == 0) {
                mu[i*p[j]] = 0;
                break;
            } else    mu[i*p[j]] = -mu[i];
        }
    }
    return;
}

和函数

继续来讨论莫比乌斯函数的和函数 G(n)：

G(n) = \sum_{d \mid n} \mu(d)

n = 1
可得 G(1)=1。
n>1
设 n = p_1^{\alpha_1}p_2^{\alpha_2}p_3^{\alpha_3}\cdots p_k^{\alpha_k}，令 n' = p_1p_2p_3\cdots p_k。

由于 \mu 在含平方因子的数处为 0，所以
G(n) = G(n') = \sum_{d \mid n'}\mu(d)
从 k 个不同质因子中选 i 个的乘积作为 d，共有 \binom{k}{i} 种选法，每种贡献 (-1)^i，所以
G(n) = \sum_{i = 0}^k \binom{k}{i}(-1)^i
使用二项式定理：
G(n) = \sum_{i = 0}^k \binom{k}{i}(-1)^i 1^{k-i} = (-1+1)^k = 0

总结一下，莫比乌斯函数的和函数的取值：

\sum_{d \mid n}\mu(d) = [n=1] = \begin{cases} 1, & n=1,\\ 0, & n\ne 1. \end{cases}

与欧拉函数的关系

已知有下列的式子

\begin{align} \varphi = \text{id} * \mu \end{align}

证明：令 n = p_1^{\alpha_1}p_2^{\alpha_2}p_3^{\alpha_3}\cdots p_k^{\alpha_k}。

则 (1) 式左边：

\begin{align} \varphi(n) &=n\prod_{i=1}^k (1 - \dfrac{1}{p_i}) \nonumber \\ &= n\left( 1-\sum_{i=1}^k \dfrac{1}{p_i} + \sum_{1\le i <j \le k}\dfrac{1}{p_ip_j} - \sum_{1\le i < j < t \le k} \dfrac{1}{p_ip_jp_t} \cdots \right) \nonumber \end{align}

$$ \begin{align} (\text{id} * \mu)(n) &= \sum_{d \mid n} \text{id}(\dfrac{n}{d})\mu \left( d\right) \nonumber \\ &= n\sum_{d \mid n} \dfrac{\mu(d)}{d} \nonumber \\ \end{align} $$ - 当 $d = 1$ 时，$\mu(d) = 1$，故第一项为 $1

当 d = p_i 时，\mu(d) = -1，故第二项为 -\sum \frac{1}{p_i}
当 d = p_ip_j 时，\mu(d) = 1，故第三项为 \sum \frac{1}{p_ip_j}
当 d = p_ip_jp_t 时，\mu(d) = -1，故第四项为 -\sum \frac{1}{p_ip_jp_t}
\cdots

将上面的式子全部加起来

(\text{id} * \mu)(n) = n\left( 1-\sum_{i=1}^k \dfrac{1}{p_i} + \sum_{1\le i <j \le k}\dfrac{1}{p_ip_j} - \sum_{1\le i < j < t \le k} \dfrac{1}{p_ip_jp_t} \cdots \right) \nonumber

故结论得证。

文章使用了 deepseek-v4-pro 进行润色。