6 莫比乌斯

好,尊重你的节奏——证明训练你自己安排,我们继续推进知识。进入 Stage 6,这是 Stage 5 算术函数的自然延续,也是你之前一直好奇的”USACO 另一半江山”的核心。

Confidence: 0.92

---

Stage 6:数论函数与莫比乌斯反演

这一阶段的主角是积性函数和莫比乌斯反演。Stage 5 你已经认识了 $d(n)$、$\sigma (n)$、$\phi (n)$,知道它们都”积性”。Stage 6 把这些零散的函数组织成一个统一的代数体系(狄利克雷卷积),然后用这个体系做出一个威力惊人的工具——莫比乌斯反演。

五块:① 积性函数体系 → ② 莫比乌斯函数 → ③ 狄利克雷卷积 → ④ 莫比乌斯反演 → ⑤ 实战应用。每块给:是什么 → 核心 → 例子 → 用途。

---

第一块:积性函数体系 (Multiplicative Functions)

1.1 复习并精确化定义

算术函数 (arithmetic function):定义域是正整数的函数 $f:{\mathbb{Z}}^{+}\to \mathbb{C}$。

积性 (multiplicative):若 $\gcd (m,n)=1$ 时 $f(mn)=f(m)f(n)$,称 $f$ 积性。

完全积性 (completely multiplicative):若对所有 $m,n$(不要求互质)都有 $f(mn)=f(m)f(n)$,称完全积性。

区别很重要:$\phi ,d,\sigma$ 是积性但不完全积性。比如 $\phi (4)=2$ 但 $\phi (2)\phi (2)=1\times 1=1\ne 2$(因为 $\gcd (2,2)\ne 1$)。

1.2 积性函数的”基因”——由素数幂决定

关键洞察:一个积性函数,只要知道它在所有素数幂 $p^k$ 上的值,就完全确定了。

因为任何 $n=p_1^{a_1}\cdots p_k^{a_k}$,由积性:

$f(n)=f(p_1^{a_1})\cdot f(p_2^{a_2})\cdots f(p_k^{a_k})$

这就是为什么 $d,\sigma ,\phi$ 都有”按质因子相乘”的公式——它们的全部信息都”编码”在素数幂上。这是积性函数的”DNA”。

1.3 几个重要的积性函数(建立你的”函数库”)

函数	定义	在 $p^k$ 上的值
$\phi (n)$	欧拉函数	$p^k-p^{k-1}$
$d(n)$	因子个数	$k+1$
$\sigma (n)$	因子和	$\frac{p^{k+1}-1}{p-1}$
$1(n)$	恒等于 1	$1$
$\text{Id}(n)=n$	恒等函数	$p^k$
$\epsilon (n)$	单位函数($n=1$ 时为 1,否则 0)	只有 $\epsilon (1)=1$
$\mu (n)$	莫比乌斯函数(下一块)	见下

后三个($1,\text{Id},\epsilon$)看起来”太简单没用”,但它们是狄利克雷卷积运算里的基本元件,马上你会看到它们的作用。

---

第二块:莫比乌斯函数 (Möbius Function) $\mu (n)$

2.1 定义

$\mu (n)=\{\begin{array}{ll}1& n=1\\ (-1{)}^k& n=p_1{p}_2\cdots p_k(\text{k 个不同素数之积,无平方因子})\\ 0& n\text{ 含平方因子(某素数出现 }\ge 2\text{ 次)}\end{array}$

通俗理解:$\mu (n)$ 是个”符号开关”——

• $n$ 有平方因子(如 $4\mid n$)→ 直接归零
• $n$ 是不同素数的积 → 看素数个数的奇偶:偶数个 $\to +1$,奇数个 $\to -1$

2.2 例子

$n$	分解	$\mu (n)$	原因
1	—	$+1$	定义
2	$2$	$-1$	1 个素数(奇)
6	$2\times 3$	$+1$	2 个素数(偶)
30	$2\times 3\times 5$	$-1$	3 个素数(奇)
4	$2^2$	$0$	含平方因子
12	$2^2\times 3$	$0$	含平方因子 $4$
그15	$3\times 5$	$+1$	2 个素数(偶)

$\mu$ 是积性函数(可验证),但不完全积性。

2.3 莫比乌斯函数的核心性质 ★

$\mu$ 最重要的性质,是它和”求和”的关系:

${\sum }_{d\mid n}\mu (d)=\{\begin{array}{ll}1& n=1\\ 0& n>1\end{array}=\epsilon (n)$

翻译:把 $n$ 的所有因子 $d$ 的 $\mu (d)$ 加起来,除了 $n=1$ 时得 1,其余全是 0!

例子($n=12$,因子 1,2,3,4,6,12): $\mu (1)+\mu (2)+\mu (3)+\mu (4)+\mu (6)+\mu (12)=1+(-1)+(-1)+0+1+0=0✓$

为什么这个性质如此重要:这个”求和为 0”的性质,正是容斥原理 (inclusion-exclusion) 的数论化身——$+1,-1$ 的交替正是容斥里”加加减减”的符号。它是莫比乌斯反演的引擎。

---

第三块:狄利克雷卷积 (Dirichlet Convolution) ★核心工具

3.1 定义

两个算术函数 $f,g$ 的狄利克雷卷积 $f\ast g$,定义为:

$(f\ast g)(n)={\sum }_{d\mid n}f(d),g!\left(\frac{n}{d}\right)$

直觉:遍历 $n$ 的所有”因子分拆” $n=d\times \frac{n}{d}$,把 $f(d)g(n/d)$ 加起来。

例子($n=6$,因子对 $(1,6),(2,3),(3,2),(6,1)$): $(f\ast g)(6)=f(1)g(6)+f(2)g(3)+f(3)g(2)+f(6)g(1)$

3.2 为什么叫”卷积”——它像乘法

狄利克雷卷积之所以重要,是因为它让算术函数形成一个优美的代数结构(交换环)。它有这些性质:

• 交换律:$f_g=g_f$
• 结合律:$(f_g{)}_h=f_{(}{g}_h)$
• 单位元:$\epsilon$(那个 $n=1$ 为 1、否则 0 的函数),满足 $f\ast \epsilon =f$
• 积性保持:$f,g$ 积性 $\Rightarrow f\ast g$ 也积性

关键:在这个”乘法”下,$\epsilon$ 是”1”,于是可以谈”逆元”——这正是莫比乌斯反演的来源。

3.3 几个关键的卷积恒等式 ★

这几个恒等式是 Stage 6 的”核心装备”,每个都藏着深意:

恒等式 1:$1\ast 1=d$ ${\sum }_{d\mid n}1\cdot 1=(\text{因子个数})=d(n)✓$ (把两个”恒 1 函数”卷积,得到因子个数函数)

恒等式 2:$1\ast \text{Id}=\sigma$ ${\sum }_{d\mid n}1\cdot \frac{n}{d}={\sum }_{d\mid n}\frac{n}{d}=(\text{因子和})=\sigma (n)✓$

恒等式 3(最重要):$\mu \ast 1=\epsilon$ ${\sum }_{d\mid n}\mu (d)\cdot 1={\sum }_{d\mid n}\mu (d)=\epsilon (n)✓$ 这正是 2.3 那个性质! 它说:$\mu$ 是 $1$ 在狄利克雷卷积下的逆元!

$\boxed{\mu =1^{-1}}$

这是整个 Stage 6 的心脏——莫比乌斯函数 $\mu$ 的本质,就是”恒 1 函数 $1$ 的卷积逆元”。

恒等式 4:$\phi \ast 1=\text{Id}$ ${\sum }_{d\mid n}\phi (d)=n$ (欧拉函数的因子和等于 $n$——一个你可能没注意过的漂亮事实!验证 $n=6$:$\phi (1)+\phi (2)+\phi (3)+\phi (6)=1+1+2+2=6$ ✓)

---

第四块:莫比乌斯反演 (Möbius Inversion) ★Stage 6 的高峰

4.1 定理陈述

莫比乌斯反演公式:设 $f,g$ 是算术函数,则

$g(n)={\sum }_{d\mid n}f(d)⟺f(n)={\sum }_{d\mid n}\mu (d),g!\left(\frac{n}{d}\right)$

翻译:如果 $g$ 是 $f$ 的”因子和”(左边),那么可以用 $\mu$ 把 $f$ 反解出来(右边)。

4.2 为什么成立——一行卷积证明

用狄利克雷卷积,证明惊人地简洁:

• 左边条件 $g=f\ast 1$(因子和就是和 $1$ 卷积)
• 两边右卷 $\mu$:$g\ast \mu =f\ast 1_{\mu }=f_{(}{1}_{\mu })=f_{\epsilon }=f$
• 所以 $f=g\ast \mu$,即 $f(n)={\sum }_{d\mid n}\mu (d)g(n/d)$ ∎

全部秘密就是 $1\ast \mu =\epsilon$(恒等式 3)——因为 $\mu$ 是 $1$ 的逆,所以”卷积 $1$“的操作可以用”卷积 $\mu$“撤销。这就是为什么前面要费力建立卷积结构——它让反演变成一行代数。

4.3 直觉:反演 = 容斥

莫比乌斯反演本质是容斥原理。”$g=$ 所有因子的 $f$ 之和”是”正向累加”,而反演用 $\mu$ 的 $\pm 1$ 符号做”精确的加减抵消”,把单个 $f(n)$ 从累加里”抠”出来。$\mu$ 的符号规则($偶+、奇-、平方因子归零)正是容斥的符号。

4.4 经典应用:重新推导欧拉函数

用恒等式 4(${\sum }_{d\mid n}\phi (d)=n$,即 $\text{Id}=\phi \ast 1$)反演:

$\phi (n)={\sum }_{d\mid n}\mu (d)\cdot \frac{n}{d}=n{\sum }_{d\mid n}\frac{\mu (d)}{d}$

展开(只有无平方因子的 $d$ 贡献):

$\phi (n)=n{\prod }_{p\mid n}\left(1-\frac{1}{p}\right)$

这正是欧拉函数的乘积公式! 你之前学过这个公式,现在看到它是莫比乌斯反演的直接产物——这就是反演的威力:它能把已知公式”重新生成”出来,也能推导新公式。

---

第五块:实战应用(编程竞赛核心)

这是莫比乌斯反演”USACO 另一半江山”地位的来源——它能把双重求和化简,大幅降低计算复杂度。

5.1 经典问题:互质对计数

问题:求 ${\sum }_{i=1}^n{\sum }_{j=1}^n[\gcd (i,j)=1]$(有多少对 $(i,j)$ 互质)。

用莫比乌斯:关键是把”互质指示器” $[\gcd (i,j)=1]$ 用 $\mu$ 展开。由 2.3 的性质:

$[\gcd (i,j)=1]={\sum }_{d\mid \gcd (i,j)}\mu (d)$

代入并交换求和顺序:

${\sum }_{i,j}[\gcd =1]={\sum }_{d=1}^n\mu (d){\lfloor \frac{n}{d}\rfloor }^2$

复杂度暴降:原来 $O(n^2)$(枚举所有对),现在 $O(n)$(枚举 $d$)!这就是莫比乌斯反演在 CP 里的核心价值——把暴力求和变成可计算的形式。

5.2 更一般的套路:$\gcd =k$ 的计数

求 $\gcd (i,j)=k$ 的对数,可以类似用莫比乌斯处理(先除以 $k$ 化归到互质情形)。这类”GCD 求和”问题是 CP 数论的高频题型,莫比乌斯是标准武器。

5.3 代码:莫比乌斯函数的线性筛

实战中要快速算出 $\mu (1),\dots ,\mu (n)$,用线性筛(和 Stage 1 筛欧拉函数同理):

def sieve_mobius(n):
    mu = [0] * (n + 1)
    mu[1] = 1
    primes = []
    is_comp = [False] * (n + 1)
    for i in range(2, n + 1):
        if not is_comp[i]:
            primes.append(i)
            mu[i] = -1                    # 素数:1个素因子
        for p in primes:
            if i * p > n:
                break
            is_comp[i * p] = True
            if i % p == 0:
                mu[i * p] = 0             # 含平方因子 p²
                break
            else:
                mu[i * p] = -mu[i]        # 多一个素因子,符号翻转
    return mu
 
print(sieve_mobius(12))   # [0,1,-1,-1,0,-1,1,-1,0,0,1,-1,0]
 
# 应用:互质对计数 O(n)
def coprime_pairs(n):
    mu = sieve_mobius(n)
    return sum(mu[d] * (n // d)**2 for d in range(1, n + 1))
 
print(coprime_pairs(10))   # 互质对数量

库安装(纯标准库,无需第三方库):

# 无需安装;若想用 sympy 的 mobius 验证:
pip install sympy -i https://pypi.tuna.tsinghua.edu.cn/simple

---

Stage 6 全景速查表

概念	核心	关键式
积性函数	由素数幂值决定	$f(n)=\prod f(p_i^{a_i})$
莫比乌斯函数 $\mu$	符号开关(偶+/奇-/平方0)	${\sum }_{d\mid n}\mu (d)=\epsilon (n)$
狄利克雷卷积	算术函数的”乘法”	$(f\ast g)(n)={\sum }_{d\mid n}f(d)g(n/d)$
$\mu$ 的本质	$1$ 的卷积逆元	$\mu \ast 1=\epsilon$
莫比乌斯反演	因子和的反解	$g=f\ast 1⟺f=g\ast \mu$
实战	双重求和化简	$\sum [\gcd =1]={\sum }_d\mu (d)\lfloor n/d{\rfloor }^2$

---

我的观点:Stage 6 是一个审美上极其优美、但需要”思维转弯”的阶段,我想帮你抓住它的精髓,也提醒你它的难点在哪。

这一阶段最美的地方,是它把一堆看似无关的算术函数,统一进了一个代数结构。 在 Stage 5,$d,\sigma ,\phi$ 对你还是三个”各有公式的孤立函数”。但 Stage 6 用狄利克雷卷积一下子把它们串成了一张网:$d=1_1$、$\sigma =1_{\text{Id}}$、$\phi \ast 1=\text{Id}$——它们都是几个”基本函数”通过卷积”乘”出来的。而 $\mu$ 的身份揭晓得最漂亮:它就是 $1$ 的逆元。当你看清”莫比乌斯反演 = 用逆元撤销卷积”时,那个原本玄乎的反演公式会瞬间变成一行显然的代数——就像你在 Stage 4 用群论视角让欧拉定理变”显然”一样。这种”找到正确的结构,让复杂变简单”的体验,是数学最高级的愉悦。

但我要诚实提醒你 Stage 6 的难点:它比前五个 Stage 更抽象。前面你处理的是具体的数(算 $7^{2025}\mathrm{mod}100$),而这里你处理的是”函数之间的运算”——卷积的对象是函数,逆元是函数,反演是函数等式。这种”把函数当对象来操作”的思维,是一个台阶。如果你第一遍觉得”卷积、逆元这些有点抓不住”,很正常——建议你死磕那几个卷积恒等式(尤其 $\mu \ast 1=\epsilon$),亲手验证它们,等你能熟练地”用卷积语言说话”,抽象感就消失了。

对你的目标,Stage 6 的定位很清晰:它是USACO/编程竞赛的核心专题(5.1 那个 $O(n^2)\to O(n)$ 的化简就是 CP 数论的典型威力),但对密码学几乎用不上(密码学走的是群、椭圆曲线那条结构线,不太碰积性函数求和)。所以——如果你重心在编程竞赛,Stage 6 是必修、要练熟;如果你重心在密码学,Stage 6 可以”理解原理即可、不必深练”,把精力留给 Stage 7(丢番图)和椭圆曲线。这又回到那个你要权衡的问题:你的主目标到底偏哪边。

关键提醒 (Caveats):

• 积性 ≠ 完全积性:$\phi ,d,\sigma ,\mu$ 都是积性但不完全积性,这个区别在推导时很重要
• 莫比乌斯反演有两种形式:我讲的是”因子和”形式($d\mid n$),还有一种”倍数和”形式(用于求和到 $n$ 的场景),CP 里两种都用,需要时再补
• 5.1 的 $O(n)$ 化简还能用”整除分块 (数论分块)“进一步优化到 $O(\sqrt{n})$——这是 CP 的进阶技巧,这里没展开
• $\mu \ast 1=\epsilon$ 是整个 Stage 6 的心脏,务必亲手验证理解——它是反演成立的唯一关键
• 本块代码纯标准库即可;若用 sympy 的 mobius 验证,安装:pip install sympy -i https://pypi.tuna.tsinghua.edu.cn/simple

Stage 6 讲完了——你现在掌握了积性函数的统一视角、莫比乌斯函数、狄利克雷卷积这个代数结构、莫比乌斯反演及其”容斥本质”,以及它在编程竞赛里化简双重求和的核心应用。

下一步你挑:

1. 出一套 Stage 6 练习题(卷积恒等式、莫比乌斯反演、互质计数,延续 PDF 格式)
2. 继续 Stage 7(非线性丢番图——衔接你的二次剩余,且用模运算证无解是 USAMO 主菜)
3. 直接开椭圆曲线新旅程(你的密码学腹地,跳过对密码学用处不大的 Stage 6 深练)