莫比乌斯函数学习笔记

ryderyang · 2025-07-02 10:23:46 · 算法·理论

积性函数

若函数 f(n) 满足：

f(1) = 1
若正整数 a 与正整数 b 互质，则 f(a \times b) = f(a) \times f(b) 。

则称这个函数为积性函数，若对于任意 a、b 都成立，则称这个函数为完全积性函数。

狄利克雷卷积

定义两个数论函数 f 和 g 的狄利克雷卷积为：

h(n)=\sum_{d \mid n} f(d) \times g(\frac{n}{d})

一个性质：若 f 和 g 都是积性函数，则函数 h 也是积性函数。

莫比乌斯函数

莫比乌斯函数的定义是：

如果 n=1，则 \mu(n)=1。
如果 n 的因子中有大于 1 的平方数，则 \mu(n)=0。
如果 n 是无平方因子的数，且 n 是 k 个质数的积，也就是 n=p_1 \times p_2 \times \dots \times p_k，其中 p_i 是互不相同的质数，则 \mu(n) = (-1)^k。

莫比乌斯函数是积性函数。

证明：设正整数 n 和 m 互质。若 n 或 m 中有平方因子，则 n \times m 也有这个因子。\mu(n \times m) =\mu(n) \times \mu(m) = 0，符合条件。否则，设 n 有 s 个质因子，m 有 t 个质因子。则 \mu(n \times m) = (-1)^{s+t} = (-1)^s \times (-1)^t = \mu(n) \times \mu(m)，符合条件。

莫比乌斯函数有一个性质：

如果 n=1，则 \sum_{d \mid n} \mu(d) = 1。
否则，\sum_{d \mid n} \mu(d) = 0。

证明：n=1 的情况证明起来非常简单，因为他只有一个因子 1。对于其他的 n \ne 1，我们可以令 n = p_1^{a_1} \times p_2^{a_2} \times \dots \times p_k^{a_k}。

若 n 没有平方因子，则他的因数就是所有 p_i 的子集乘积。对于每一个子集大小为 m 的因数 d，都有 \mu(d) = m。所以：
\sum_{d \mid n} \mu(d) = \sum_{m=0}^{k} \binom{k}{m} \times (-1)^m=(1-1)^k=0
若 n 有平方因子，对于所有的平方因子 d，都肯定满足 \mu(d)=0，所以他们都是没用的，不需要管。剩下的那些就跟前面证明过的一样了。

线性筛求莫比乌斯函数

只需在标记合数的部分再加上一个莫比乌斯函数的就行了，详细方法见我的这篇题解。

简单来说，就是令 j = i \times p。

如果 i 是 p 的倍数，则 \mu(j) = 0，因为他有平方因子。
否则 \mu(j)= \mu(i) \times \mu(p) = \mu(i) \times (-1)。

一道简单的例题

前置知识：数论分块，如果你们不会，可以看我的这篇文章。

我们先看题目。

人话：求 \sum_{i=1}^{a} \sum_{j=1}^{b} [\gcd(i,j) = d]。

解题思路

式子等同于求 \sum_{i=1}^{\lfloor \frac{a}{d} \rfloor} \sum_{j=1}^{\lfloor \frac{b}{d} \rfloor} [\gcd(i,j)=1]。

根据莫比乌斯的性质，可以得到：

ans=\sum_{i=1}^{\lfloor \frac{a}{d} \rfloor} \sum_{j=1}^{\lfloor \frac{b}{d} \rfloor} \sum_{k \mid \gcd(i,j)} \mu(k)

调换求和顺序，得：

ans= \sum_{k=1}^{n} \mu(k) \sum_{i=1}^{\lfloor \frac{a}{k \times d} \rfloor} \sum_{j=1}^{\lfloor \frac{b}{k \times d} \rfloor} 1

消掉一些没用的循环：

ans= \sum_{k=1}^{n} \mu(k) \times \lfloor \frac{a}{k \times d} \rfloor \times \lfloor \frac{b}{k \times d} \rfloor

然后就是我在数论分块里讲到的二维数论分块了。

莫比乌斯反演

我们设 f 和 g 是两个数论函数。

定理指出：如果对于任意正整数 n 有：

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

那么：

f(n) = \sum_{d \mid n} \mu(\frac{n}{d})\times g(d)

什么！这都能扯到莫比乌斯函数！太逆天了！

证明：假设 g(n) = \sum_{d \mid n} f(d)，我们需要证明：
f(n)=\sum_{d \mid n} \mu(\frac{n}{d}) \times g(d)
把已知条件代入：
f(n)=\sum_{d \mid n} \mu(\frac{n}{d}) \times \sum_{k \mid d} f(k)。
有点难看，把两个循环搞一起：
f(n)=\sum_{d \mid n} \sum_{k \mid d} \mu(\frac{n}{d}) \times f(k)
观察一下这两个循环，d \mid n，且 k \mid d，所以 k \mid n。我们可以设 d = k \times s，那么 (k \times s) \mid n，也就是 s \mid \frac{n}{k}。所以：
f(n)=\sum_{k \mid n} f(k) \times \sum_{s \mid \frac{n}{k}} \mu(\frac{n}{k \times s})
因为 \frac{n}{k \times s} = \frac{\frac{n}{k}}{s}，所以：
\sum_{s \mid \frac{n}{k}} \mu(\frac{n}{k \times s})=\sum_{s \mid \frac{n}{k}}\mu(\frac{\frac{n}{k}}{s})。
然后，我们就会发现，这个循环其实就是遍历了 \frac{n}{k} 的因数，所以我们可以给他搞简单一点：
f(n) = \sum_{k \mid n} f(k) \times \sum_{m \mid \frac{n}{k}} \mu(m)
根据莫比乌斯函数的性质，有：

如果 n=k，则 \sum_{m \mid \frac{n}{k}} \mu(m) = 1。

否则，\sum_{m \mid \frac{n}{k}} \mu(m) = 0。

所以：
\sum_{k \mid n} f(k) \times \sum_{m|\frac{n}{k}} \mu(m) = f(n) \times 1 + \sum_{k \mid n,k \ne n} f(k) \times 0 = f(n)
证毕。