企业官网建设流程全解析

上周有个朋友发来一道题让我帮忙看：给一个 n，最大 10^7，求 1 到 n 所有数的约数个数之和。他说自己写了一个 O(n√n) 的版本，n 到 10^5 就卡死了，问我是不是该上个什么高级数据结构。我看了眼他的代码，第一反应不是“优化”，而是“换数学视角”。这题本质是统计有多少对 (a,b) 满足 a×b ≤ n，把枚举约数改成枚举倍数，一个调和级数就解决了。这种事情我碰到过太多次：不是题难，而是大家把数学公式当成了课本上的装饰品。

这篇文章我想把几个在算法里“低调但极其好用”的数学公式系统地聊一遍。我会讲清楚三件事：每个公式是什么、为什么在算法里有用、用的时候有哪些坑。内容覆盖调和级数、斯特林公式、费马小定理、贝叶斯公式和拉格朗日插值。适合正在刷题的人、准备面试的人、写工程代码的人，以及所有对“算法背后的数学直觉”感兴趣的人。

1. 从一道“约数统计”题说起：公式到底被谁忽视了

1.1 一个常见到让人忽略的暴力写法

题目是这样的：给定 n，求 1 到 n 所有数的约数个数之和。大部分人的第一版代码长这样：对每个 i，用从 1 到 √i 的循环数约数。单看一个数，√i 并不大，但所有数加起来就是 Σ√i，约等于 (2/3)n^1.5。n 到 10^7 时，这个量级是十亿次级别，本地跑完得几十秒，放到在线评测系统里基本就是超时。

我当时问那个朋友：你有没有想过，约数这个东西是“成对出现”的？一个正整数 i 如果有一个约数 d，那么一定存在一个配对约数 i/d。所以“1 到 n 的所有约数”本质上就是所有满足 a×b ≤ n 的有序数对 (a,b)。这句话看起来像废话，但把它写下来，问题的复杂度就变了。

1.2 为什么第一反应不是数学，而是“加个缓存”

很多人的第一反应是：用筛法预处理每个数的约数表，然后累加；或者用记忆化缓存已经算过的约数个数。这些做法不是不行，而是没有抓住问题的本质。筛法预处理约数个数确实可以做到 O(n log n)，但前提是你已经知道“枚举倍数”这个套路；如果不知道，你还是会陷入“对每个数单独分解”的思维定式。

我的观点是：数据结构是战术，数学是战略。遇到计数类问题，先别急着写代码，先在草稿纸上把问题翻译成一个数学表达式。很多时候，表达式一变形，复杂度就自动降下来了。这也是为什么我特别想写这篇文章——数学公式不是拿来背的，是拿来对问题做“变形”的。

1.3 这篇文章要聊的五个公式，一句话版

为了让你有个整体印象，我先把后面要展开的几个公式列在这里：

• 调和级数：H_n = 1 + 1/2 + ... + 1/n ≈ ln n + γ，用来估计算法里“枚举倍数”这类循环的真实复杂度。
• 斯特林公式：n! ≈ √(2πn)(n/e)^n，用来估算阶乘量级、组合数大小和概率。
• 费马小定理：a^(p-1) ≡ 1 (mod p)，用来在模素数意义下求逆元，本质是“取模世界里的除法”。
• 贝叶斯公式：P(A|B) = P(B|A)P(A)/P(B)，用来做概率推理，也是很多机器学习算法的底层框架。
• 拉格朗日插值：给定 k+1 个点，构造一个 k 次多项式穿过所有点，用来在稀疏样本之间做精确估计。

这五个公式的共同特点是：教科书里都有，但算法课不怎么强调，刷题时也容易被跳过。但它们在关键时刻能省掉一整层循环，或者把一个看似无法下手的题变成套公式。

2. 调和级数：复杂度分析里那个假装是 log 的隐藏常数

2.1 从计数约数到枚举倍数：双层循环的复杂度真相

回到刚才的约数统计问题。既然约数是成对出现的，我们反过来考虑：对于每个正整数 a，它能作为多少个数的约数？答案是 floor(n/a)，也就是 a 的倍数在 1 到 n 中的个数。于是总数就是：

Σ_{a=1}^{n} floor(n/a) ≈ n × H_n ≈ n ln n + γn

这个式子看着抽象，我换成代码你就懂了：

cnt = 0 for a in range(1, n + 1): for b in range(a, n + 1, a): # 步长是a，也就是枚举a的倍数 cnt += 1

内层循环的次数是 n/a，所以总次数是 n/1 + n/2 + ... + n/n。这是典型的调和级数求和。很多人看到双重循环就默认是 O(n²)，但这个内层循环的步长不是 1，而是 i，总次数只有 n ln n。

举一个具体的数字：n = 10000 时，Σ floor(n/i) 大约是 93648。你自己心里想一下，一个双层循环只执行不到十万次，这和你印象里的“O(n²) 一定爆炸”完全不同。所以以后看到内层步长是外层变量的循环，先算一算 Σ n/i，而不是直接写个 O(n²) 的帽子扣上去。

2.2 埃氏筛的 O(n log log n) 到底从哪来

埃氏筛是另一个调和级数思想的经典案例。你要筛出 1 到 n 的所有素数，做法是从 2 开始，把每个素数的倍数都标记为合数。表面上的循环是：

is_prime = [True] * (n + 1) is_prime[0] = is_prime[1] = False for i in range(2, int(n ** 0.5) + 1): if is_prime[i]: for j in range(i * i, n + 1, i): is_prime[j] = False

内层循环的次数是 (n - i²) / i，对所有素数 i 求和。这里面用到一个数论结论：不超过 n 的素数倒数和大约是 ln ln n 加一个常数。把 n 提出来，总标记次数就是 n × ln ln n 的量级，所以复杂度写作 O(n log log n)。

这个 log log n 非常反直觉。ln ln 10^12 大约是 3.3，也就是说 n 到了一万亿，这个复杂度的“隐常数”也才三倍多。这也是为什么埃氏筛在实际跑起来快到离谱。如果你只看“两层循环”就认定它是 O(n√n)，那你根本没有理解筛法的本质。理解调和级数之后，你会发现所谓的“线性筛”和“埃氏筛”之间的差距，并没有你想象的那么大。

2.3 一段能直接跑的调和级数代码

回到约数统计问题，最直接的写法就是用倍数枚举统计每个数的约数个数：

def divisor_count_sum(n): cnt = [0] * (n + 1) for d in range(1, n + 1): for multiple in range(d, n + 1, d): cnt[multiple] += 1 return sum(cnt[1:])

这个代码的时间复杂度是 O(n log n)，空间是 O(n)。n 取 10^7 时，内层总执行次数约等于 1.6×10^8，在 C++ 里可以在一秒多跑完，Python 会慢一些。如果你想进一步优化到 O(n)，可以用线性筛维护每个数的最小素因子，然后递推约数个数，但那是另一种思路，不是这篇文章的重点。

这里有一个工程层面的坑：上面的代码虽然复杂度可以接受，但内存访问是跳跃的。尤其是 n 很大的时候，每次 cnt[multiple] += 1 都会触碰到不同的 cache line，实际耗时可能比理论复杂度高不少。如果你在性能敏感场景里写这种代码，可以考虑分块处理，或者用数组填充配合连续访问的写法。不过在算法题里，n ≤ 10^7 这个量级通常不需要为了 cache 优化折腾，知道有这回事就行。

2.4 记忆点：看到 n/i 的求和，第一反应是 H_n

我自己用调和级数最多的场景不是约数统计，而是分析各种“均摊复杂度”。比如分块处理、跳跃表更新、并查集按秩合并的势能分析，背后都有调和级数的影子。一个特别有用的直觉是：ln n 的值远比你想象的小。ln 1000 ≈ 6.9，ln 10^6 ≈ 13.8，ln 10^9 ≈ 20.7。所以 n log n 在 n=10^6 时只是 1400 万次操作，这在绝大多数评测环境下都能接受。

以后看到形如“for i in 1..n: for j in step i:”的代码，不要急着喊 O(n²)。先在草稿纸上写一个 Σ n/i，再想想它等于 nH_n。光是这一个习惯，就能帮你少写很多“过度优化”的代码。

3. 斯特林公式：阶乘量级的“目测尺”

3.1 为什么需要一把尺子

阶乘是组合数学和概率论里最常见的量，但它的增长速度非常反直觉。你背过 20! = 2432902008176640000，大约 2.4×10^18，已经超过 64 位整数的上限；100! 更是大到 9.33×10^157。在算法题里，阶乘经常不是作为最终结果出现，而是作为中间量参与概率估算、组合数比较、期望计算。如果每一步都精确计算，很快就会溢出或者超时。

这时候你需要一把“目测尺”。斯特林公式就是这把尺子：

n! ≈ √(2πn) × (n / e)^n

它可以精确到什么程度？相对误差大约是 1/(12n)。n=10 时误差约 0.8%，n=100 时误差约 0.08%，n=1000 时误差约 0.008%。如果你只是要量级，这个精度完全够用。

3.2 公式长什么样，误差有多大

斯特林公式最常见的写法是：

n! ≈ √(2πn) (n/e)^n

更精确的版本还包含一个修正项：

n! ≈ √(2πn) (n/e)^n × (1 + 1/(12n) + 1/(288n²) - ...)

在算法题里，通常只需要取前三项的对数形式就够了。为什么？因为很多题目要的不是阶乘本身，而是“多少位”或者“概率是否大于某个阈值”，这时候对数域是唯一不会溢出的选择。

判断一个数的十进制位数，本质是求 log10，然后取整数加一。结合斯特林公式：

log10(n!) = n log10 n - n log10 e + 0.5 log10(2πn)

我来演示一个实际计算：100! 的位数。

• log10 100 = 2，n log10 n = 200
• log10 e ≈ 0.4343，n log10 e ≈ 43.43
• 0.5 log10(2π×100) ≈ 0.5 × 2.798 ≈ 1.399
• 合计 ≈ 200 - 43.43 + 1.399 ≈ 157.97
• 位数 = 158

而 100! 真实值就是 158 位数。你看，不用算完整乘积，两三行心算就能确定位数。这种能力在估算复杂度、估算搜索空间时特别管用。

3.3 用对数形式估算位数和概率

来看一个稍微复杂一点的例子：估算从 52 张牌里随机抽 13 张的组合数 C(52,13) 的量级。

先用对数形式展开：

log10 C(52,13) = log10(52!) - log10(13!) - log10(39!)

用斯特林公式分别算，得到的结果约等于 11.6 亿？不对，实际上 C(52,13) ≈ 6.35×10^11，log10 约 11.80。用斯特林公式估算误差在 0.1 以内，完全够用。

另一个典型场景是“生日悖论”。要估算 50 个人里面存在两个人生日相同的概率，可以算“都不相同”的概率：P = (365/365)(364/365)...(316/365)。这个乘积直接用浮点算会非常小，容易下溢，但取 log 之后就是一个很漂亮的求和。用 log 方法算出的概率大约 0.97，和精确值几乎一致。

3.4 代码实现与精度陷阱

在工程代码里，最好不要手写斯特林公式的浮点部分，直接用标准库的对数伽马函数最稳。Python 里是math.lgamma，C++ 里是std::lgamma。

import math def log10_fact(n): # math.lgamma(n+1) 返回 ln(n!) return math.lgamma(n + 1) / math.log(10) def approx_choose_log10(n, k): return log10_fact(n) - log10_fact(k) - log10_fact(n - k)

这里有一个很容易踩的坑：lgamma返回的是自然对数，不是常用对数。如果你想直接得到十进制位数，记得除以ln(10) ≈ 2.302585。另外，lgamma对非常小的 n 也有定义，但 n=0 或 n=1 时直接返回 0，不需要走近似公式。

还有一个很多人忽略的点：斯特林公式是“近似”，不是“精确”。如果你拿它去求一个精度要求达到 1e-15 的浮点结果，那你会被误差坑到。它的定位是量级估算和对数域计算，不是替代精确计算。在算法题里，需要精确阶乘取模时，应该预处理阶乘表或使用质因数分解，而不是用斯特林公式硬凑。

4. 费马小定理：模运算里的“除法替身”

4.1 取模世界里的除法为什么不能直接做

在整数世界里，a/b 就是 a 乘以 b 的倒数。但在取模世界里，分数没有直接意义。比如在模 7 意义下，2/3 到底是多少？你没法直接说 0.666...，因为模算术只接受整数。正确的做法是找一个整数 x，使得 3x ≡ 2 (mod 7)。如果模数是素数，那么基本上每个非零元素都有乘法逆元，除法就能变成“乘以逆元”。

问题变成了：怎么高效求一个数在模 p 意义下的逆元？最常用的方法之一，就是费马小定理。

4.2 费马小定理怎么来的

费马小定理说的是：如果 p 是素数，a 是任意不被 p 整除的整数，那么

a^(p-1) ≡ 1 (mod p)

这个定理的证明非常漂亮。考虑集合 {a, 2a, 3a, ..., (p-1)a}，在模 p 意义下，这些数恰好是 1 到 p-1 的一个排列。把它们全部乘起来，得到：

a^(p-1) × (p-1)! ≡ (p-1)! (mod p)

因为 (p-1)! 在模 p 下不等于 0，可以约掉，就得到了 a^(p-1) ≡ 1。

利用这个结论，a × a^(p-2) ≡ a^(p-1) ≡ 1，所以 a 的逆元就是 a^(p-2) mod p。这是求逆元最简单的方法，因为它不需要任何前置知识，只要会快速幂。

4.3 快速幂求逆元：代码与边界

快速幂的实现几乎是模板级的：

def mod_pow(a, e, p): a %= p r = 1 while e: if e & 1: r = r * a % p a = a * a % p e >>= 1 return r def mod_inv(a, p): # 要求 p 是素数，且 a 和 p 互质 return mod_pow(a, p - 2, p)

这个代码在 p 是素数且 a % p != 0 的时候是正确且高效的，复杂度是 O(log p)。但在 C++ 里写的时候要注意乘法溢出：p 如果是 1e9+7，两个数相乘大约是 1e18，刚好卡在 64 位整数边界内，但如果直接用 int 相乘一定溢出。我的习惯是直接用long long，保守一点可以用__int128做中间乘法。

有一个隐藏很深的条件：费马小定理要求 a 不被 p 整除。如果 a % p == 0，那么 a 在模 p 下没有逆元，因为这个数乘以任何整数模 p 都等于 0，不可能等于 1。很多题会故意在这种边界上设坑，尤其是当输入数据量大、你没注意取模时。

4.4 实际场景：组合数取模和哈希设计

费马小定理最常见的工程场景是组合数取模。要计算 C(n,k) mod p，其中 p 是 1e9+7 这种大素数，流程是：预处理阶乘表和阶乘逆元表，然后用公式 fac[n] * inv_fac[k] % p * inv_fac[n-k] % p。求 inv_fac 的时候，不需要对每个阶乘都做一次快速幂，只需要对最大的那个做一次快速幂，然后逆推：

fac = [1] * (n + 1) for i in range(1, n + 1): fac[i] = fac[i - 1] * i % p inv_fac = [1] * (n + 1) inv_fac[n] = mod_inv(fac[n], p) for i in range(n, 0, -1): inv_fac[i - 1] = inv_fac[i] * i % p

原理是 fac[i-1] = fac[i] / i，所以逆元也满足 inv_fac[i-1] = inv_fac[i] * i。

除了组合数取模，费马小定理还常用于哈希表设计中的“除法哈希”和概率算法的随机数生成。它和扩展欧几里得是两种并列的求逆元方案：模数是素数时选费马，模数是合数时用扩展欧几里得。不要混着来。

5. 贝叶斯公式：被“最大似然”挤出视野的先验

5.1 一个反直觉的概率题

先来做一道选择题：某种罕见病在人群中的发病率是 0.1%。有一种检测手段，如果一个人真的患病，检测阳性的概率是 99%；如果一个人没患病，检测阳性的概率是 1%（假阳性率）。现在有一个人的检测结果是阳性，请问他真正患病的概率是多少？

一半以上的人会脱口而出“99%”，因为检测准确率听起来很高。但实际上答案是大约 9%。计算过程就是贝叶斯公式：

P(患病 | 阳性) = P(阳性 | 患病) × P(患病) / P(阳性)

其中 P(阳性) 要展开成两部分：患病且阳性 + 未患病且假阳性。也就是：

0.99 × 0.001 / (0.99 × 0.001 + 0.01 × 0.999) ≈ 0.090

看到没？一个 99% 准确的检测，阳性后真实患病概率只有 9%。原因是发病率太低了，假阳性人数远远超过真实患者人数。这道题在算法面试里出现过不止一次，它考的根本不是概率计算能力，而是你有没有“先验”这个概念。

5.2 贝叶斯公式拆解：先验、似然、后验

贝叶斯公式的标准形式是：

P(A|B) = P(B|A) × P(A) / P(B)

三个关键角色：

• P(A) 是“先验概率”，指在看到数据 B 之前，你对事件 A 的判断。
• P(B|A) 是“似然”，指在 A 为真的前提下，观察到 B 的概率。
• P(A|B) 是“后验概率”，指观察到 B 之后，你对事件 A 的更新判断。

很多机器学习初学者只盯着似然 P(B|A)，认为“哪个假设能让数据出现的概率最大，就选哪个”。这就是最大似然估计。但最大似然有一个盲区：它忽略了先验。如果先验非常低，即使似然很高，后验也可能很低。正则化在数学上就是给参数加了一个先验分布，比如 L2 正则等价于假设参数服从均值为 0 的高斯分布。很多博客讲正则化只知道“惩罚复杂度”，不知道它其实是贝叶斯框架的自然推论。这就是被忽视的地方。

5.3 朴素贝叶斯分类的最小实现

贝叶斯公式在工程里最常见的落地是朴素贝叶斯分类器。它的核心假设是：在给定类别 c 的条件下，各个特征之间相互独立。于是：

P(c | x) ∝ P(c) × Π P(x_i | c)

以文本分类为例，特征是“单词是否出现”，类别是“垃圾邮件”和“正常邮件”。训练时统计每个词在两个类别里的出现概率，以及两类的先验 P(垃圾) 和 P(正常)。预测时对一篇文章，计算每个词在两类下的概率乘积，再乘上先验。

代码实现上有一个关键细节：要用 log 加法和，而不是概率连乘。因为一篇文章有成百上千个单词，每个词概率都在 0.01 到 0.99 之间，连乘之后很容易下溢成 0。取 log 之后，乘法变成加法，数值稳定性大幅提升。

import math def predict(words, log_p_class, log_p_word, vocab): scores = {} for c in log_p_class: s = log_p_class[c] for w in words: s += log_p_word[c].get(w, log_p_word[c]["__default__"]) scores[c] = s return max(scores, key=scores.get)

5.4 被忽视的三个工程陷阱

第一个陷阱是零概率问题。如果某个词在训练集的某个类别里一次都没出现，概率算出来是 0，连乘后整个后验变成 0。解决方案是拉普拉斯平滑：分子加 1，分母加词汇表大小。第二个陷阱是特征独立性假设几乎永远不成立。真实文本里“免费”和“点击”高度相关，但朴素贝叶斯假装它们没关系。即便如此，它在很多场景下依然表现良好，这种“错误假设但可用”的现象本身就是工程里值得习惯的。第三个陷阱是类不平衡。如果垃圾邮件只占 1%，先验就会把后验压得很低。这时单纯的贝叶斯分类阈值可能需要校准，而不是机械地选择后验最大的类别。

如果你在算法题里看到概率题，不要急着列树状图。先写一个贝叶斯公式，把分母展开，把先验写进去，很多题的答案会自动浮现出来。

6. 拉格朗日插值：给定点太少时，如何让曲线“合理地”穿过它们

6.1 插值不是拟合：数学给了一个精确解

拉格朗日插值解决的是这样一个问题：给定 k+1 个点 (x_0, y_0), (x_1, y_1), ..., (x_k, y_k)，并且所有 x_i 互不相同，我们要找一个不超过 k 次的多项式，让它在每个给定点上都取到对应的 y 值。这和“拟合”不一样，拟合是找一条近似贴近数据的曲线，插值是要求严格穿过所有已知点。

为什么算法里需要这东西？因为有些题目会故意只给你很少的信息：比如给出某个函数在 0, 1, 2, ..., k 这些点上的取值，让你求这个函数在 n 处的值，并且 n 可以非常大，大到没法直接递推。如果一个函数本质上是多项式，那你只需要 k+1 个点就能完全确定它，然后直接算 n 处的值。这就是拉格朗日插值的威力。

6.2 公式的直觉与 O(k²) 实现

拉格朗日插值的公式长这样：

L(x) = Σ_{i=0}^{k} y_i × Π_{j≠i} (x - x_j) / (x_i - x_j)

看着吓人，但直觉非常朴素。对每一个 i，构造一个“只有在 x_i 处等于 1，在其他所有已知点处等于 0”的基函数，然后把它乘上 y_i，再加起来。这样在任意一个已知点 x_i 处，只有第 i 项起作用，其他项都是 0，所以多项式必然精确穿过所有已知点。

一个最直观的实现是两重循环：

def interpolate(xs, ys, x): total = 0 k = len(xs) for i in range(k): term = ys[i] for j in range(k): if i != j: term *= (x - xs[j]) / (xs[i] - xs[j]) total += term return total

复杂度是 O(k²)。对大多数题目 k 在几千以内，这个复杂度完全能接受。

6.3 优化到 O(k)：前缀后缀积技巧

如果你要在大量 x 上反复求值，O(k²) 可能不够。优化方法也不复杂：预先算好分母 denom[i] = Π_{j≠i} (x_i - x_j)，以及分子中 x 相关的部分。关键是分子可以拆成“前缀积 × 后缀积”：

• pref[j] = Π_{t=0}^{j-1} (x - x_t)
• suf[j] = Π_{t=j+1}^{k-1} (x - x_t)

那么第 i 项分子就是 pref[i] × suf[i]。有了前缀后缀积，计算一次 L(x) 的复杂度从 O(k²) 降到 O(k)。

这里还有一个很大的坑：当 x 恰好等于某个已知点 x_i 时，分子分母都变成 0，直接套公式会得到 0/0。正确的做法是先判断 x 是否等于某个 xs[i]，如果是，直接返回 ys[i]。很多人在这个 corner case 上翻车。

6.4 高次插值的坑：多项式很美，但别乱用

拉格朗日插值在数学上是精确解，但在浮点世界里要小心。高次多项式本身很平滑，但当你用它在区间外做外推时，结果可能剧烈震荡。经典的反例是龙格现象：对一个均匀取点的函数做高次插值，次数越高，在端点附近的误差反而越大。原因不是插值公式错了，而是高次多项式“太灵活”，为了穿过所有点，它可以剧烈弯曲。

工程上，如果你处理的是实验数据，不要用高次插值去猜测两点之间的曲线。更好的做法是分段低次插值，比如三次样条。算法题里之所以敢用高次插值，是因为很多时候取模运算让一切变成精确的整数算术，不存在浮点误差问题，多项式次数再高也不怕。这一点要分清楚：数学公式是好工具，但用错了场景，再优美的公式也会变成灾难。

自然数幂和是一个很好的正面例子。S_k(n) = 1^k + 2^k + ... + n^k 是关于 n 的 k+1 次多项式，所以只需要算出前 k+2 个点，然后用拉格朗日插值求 S_k(n) 的模值。即使 n 到了 10^18，只要 k 不大，插值都能在 O(k) 时间内算完。这种题用朴素循环肯定超时，用贝努利数又要背公式，拉格朗日插值是最容易理解也最容易写对的路线。

最后分享一个我自己的习惯。学算法这几年，我学到最值钱的一件事就是：遇到题先问自己有没有数学结构可以依赖，再想数据结构怎么配合。遇到复杂度看不懂的循环，写个 n=1000 的样例数一下执行次数，再和 H_n、ln n 对一对；遇到取模除法，第一反应是问模数是不是素数，而不是闷头实现一个除法函数；遇到概率题，先写 P(A|B) = ...，把分母展开，把先验写进去；遇到给点求值，先想拉格朗日插值能不能派上用场。这几个动作几乎成了我的条件反射。

顺便说一句，手边可以存几个常用常数：ln 2 ≈ 0.693，欧拉常数 γ ≈ 0.577，log10 e ≈ 0.4343，ln 10 ≈ 2.303。别小看它们，很多复杂度估算和手算题最后都落到这几个数上。公式本身不难，难的是你愿不愿意在写循环之前，先停下来做一分钟数学。