Arendelle Royal Library

除数求和的工具与方法

除数函数求和的技术：Dirichlet 卷积、双曲线法与常见估计。

2026.06.18 · 4 min · evolving · 数学

问题形式

处理形如

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

的求和——即遍历 \(n\) 的所有正除数 \(d\)，对 \(f(d)\) 求和。在卷积语言里这就是 \(g = f * \mathbf 1\)，其中 \(\mathbf 1(n) = 1\)。

工具总览

工具适用场景要点
狄利克雷卷积统一框架\(g = f * \mathbf 1\)，结合律/交换律/分配律成立
积性函数化简\(f\) 是积性函数\(g\) 也是积性的，只算素数幂 \(p^k\) 再乘起来
莫比乌斯反演已知 \(g\)，还原 \(f\)\(f = g * \mu\)，即 \(\mu\) 是 \(\mathbf 1\) 的卷积逆元
双重求和换序嵌套 \(\sum_{n \le x} \sum_{d \mid n}\)\(\sum_{n\le x}\sum_{d\mid n} = \sum_{d\le x}\sum_{k\le x/d}\)
贝尔级数分析积性函数的卷积结构\(f_p(x) = \sum f(p^k) x^k\)，卷积变普通乘法
DGF（Dirichlet 生成函数）级数层面分析\(F(s) = \sum f(n)/n^s\)，\((f*g)\) 的 DGF 是 \(F(s)G(s)\)
欧拉乘积积性函数的 DGF\(\sum f(n)/n^s = \prod_p \left(\sum_{k\ge 0} f(p^k)/p^{ks}\right)\)

积性函数化简 —— 最实用的技巧

若 \(f\) 是积性函数（\(f(1)=1\) 且 \(\gcd(m,n)=1 \Rightarrow f(mn)=f(m)f(n)\)），则

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

也是积性函数。狄利克雷卷积保持积性。

因此只需对素数幂计算：

\(g(p^k) = f(1) + f(p) + f(p^2) + \cdots + f(p^k)\)

对一般的 \(n = \prod p_i^{e_i}\)：

\(g(n) = \prod_i g(p_i^{e_i})\)

这相当于把”对 \(n\) 的所有除数求和”降维成”对每个素因子独立求和再乘起来”。

例：除数个数函数 \(d(n) = \sum_{d\mid n} 1 = (\mathbf 1 * \mathbf 1)(n)\)。

\(f = \mathbf 1\) 是积性函数，\(d(p^k) = k+1\)，故 \(d(n) = \prod (e_i+1)\)。

例：除数和函数 \(\sigma(n) = \sum_{d\mid n} d = (\text{id} * \mathbf 1)(n)\)。

\(\sigma(p^k) = 1 + p + p^2 + \cdots + p^k = \frac{p^{k+1}-1}{p-1}\)，再对各个 \(p_i^{e_i}\) 乘起来。

莫比乌斯反演 —— 反向还原

若已知 \(g(n) = \sum_{d\mid n} f(d)\)，需要还原 \(f\)：

\(f(n) = \sum_{d\mid n} \mu(d) \cdot g\!\left(\frac{n}{d}\right) = \sum_{d\mid n} \mu\!\left(\frac{n}{d}\right) \cdot g(d)\)

在卷积语言里：\(g = f * \mathbf 1 \iff f = g * \mu\)，因为 \(\mu * \mathbf 1 = \varepsilon\)。

典型用途：

  1. 提取信息：从 \(\sum_{d\mid n} \varphi(d) = n\) 反演得 \(\varphi(n) = \sum_{d\mid n} \mu(d) \cdot n/d\)
  2. 消去除数求和层：在复杂和式中，若有 \(\sum_{d\mid n} f(d)\) 且想换成 \(f\) 本身，用反演消掉外层
  3. 加权重构：\(\sum_{d\mid n} f(d) h(n/d)\) 形式，若 \(h(1) \neq 0\)，存在唯一的卷积逆元 \(h^{-1}\)，从而 \(f = g * h^{-1}\)

双重求和换序

这是最常用的”绕过反演”的直接手段：

\(\sum_{n \le x} \sum_{d \mid n} f(d) = \sum_{d \le x} f(d) \cdot \left\lfloor \frac{x}{d} \right\rfloor\)

原理：交换求和次序，先固定除数 \(d\)，再数 \(d\) 作为多少个 \(\le x\) 的 \(n\) 的除数出现。

进阶：\(\lfloor x/d \rfloor\) 只有 \(O(\sqrt{x})\) 种不同的取值，可以分段处理，将复杂度从 \(O(x)\) 降到 \(O(\sqrt{x})\)。这就是杜教筛和数论分块的基础。

贝尔级数

对积性函数 \(f\)，定义其在素数 \(p\) 处的贝尔级数：

\(f_p(x) = \sum_{k=0}^{\infty} f(p^k) \, x^k\)

关键性质：\((f * g)_p(x) = f_p(x) \cdot g_p(x)\)，即卷积变成普通幂级数乘法。

常用贝尔级数：

\(f\)\(f_p(x)\)
\(\varepsilon\)\(1\)
\(\mathbf 1\)\(\frac{1}{1-x}\)
\(\mu\)\(1-x\)
\(\text{id}\)\(\frac{1}{1-px}\)
\(\varphi\)\(\frac{1-x}{1-px}\)
\(d(n)\)（除数个数）\(\frac{1}{(1-x)^2}\)
\(\sigma(n)\)（除数和）\(\frac{1}{(1-x)(1-px)}\)

例：\(\mu * \mathbf 1 = \varepsilon\) 在贝尔级数下就是 \((1-x) \cdot \frac{1}{1-x} = 1\)。

例：\(\varphi * \mathbf 1 = \text{id}\) 在贝尔级数下就是 \(\frac{1-x}{1-px} \cdot \frac{1}{1-x} = \frac{1}{1-px}\)。

DGF（Dirichlet 生成函数）

\(F(s) = \sum_{n=1}^{\infty} \frac{f(n)}{n^s}\)

核心性质：\((f * g)\) 的 DGF 是 \(F(s) \cdot G(s)\)。

常用 DGF：

\(f\)\(F(s)\)
\(\mathbf 1\)\(\zeta(s)\)
\(\mu\)\(1/\zeta(s)\)
\(\text{id}\)\(\zeta(s-1)\)
\(\varphi\)\(\zeta(s-1)/\zeta(s)\)
\(d(n)\)\(\zeta(s)^2\)
\(\sigma_k(n) = \sum_{d\mid n} d^k\)\(\zeta(s)\zeta(s-k)\)

DGF 把卷积变成普通乘积，适合做渐近分析和级数层面的推导。

实战路线图

面对一个除数求和问题，按以下顺序尝试：

  1. \(f\) 是积性的吗？ → 是：直接算素数幂 \(g(p^k)\)，乘积即可。问题结束。
  2. 需要反向解出 \(f\)？ → 用莫比乌斯反演：\(f = g * \mu\)。
  3. 碰到嵌套 \(\sum_{n\le x} \sum_{d\mid n}\)？ → 先换序试试；不行再用反演。
  4. 要分析卷积的代数结构？ → 切换到贝尔级数或 DGF。

参考文献