数学技巧

本章目标：掌握面试中常用的数学速算技巧和数论基础知识，培养数学直觉。

题型特点

数学技巧题不考高深理论，而是考你对基础数学的灵活运用。高斯 7 岁时就能秒算 1+2+...+100，靠的不是计算速度，而是发现规律的能力。面试中的数学技巧题同样如此——面试官想看你能否发现捷径、化繁为简。

常见考点：数列求和、整除判别、模运算、最大公约数、组合数学基础、速算技巧、不等式与极值。

---

数学基础速查

必背公式

名称	公式
等差数列前 n 项和	S_n = n(a₁ + aₙ)/2 = n·a₁ + n(n-1)d/2
等比数列前 n 项和	S_n = a₁(1 - rⁿ) / (1 - r)（r ≠ 1）
无穷等比和（|r| < 1）	S = a₁ / (1 - r)
平方和	1² + 2² + ... + n² = n(n+1)(2n+1)/6
立方和	1³ + 2³ + ... + n³ = [n(n+1)/2]²
二项式定理	(a+b)ⁿ = Σ C(n,k) aⁿ⁻ⁱ bⁱ
帕斯卡恒等式	C(n,k) = C(n-1,k-1) + C(n-1,k)
范德蒙德恒等式	C(m+n,k) = Σ C(m,i)·C(n,k-i)

重要恒等式

• 几何级数：1 + x + x² + ... = 1/(1-x)，|x| < 1。
• 二项式系数倒数和：Σ_{k=0}^{n} C(n,k) / (k+1) = (2^{n+1} - 1) / (n+1)。
• Hockey Stick 恒等式：Σ_{i=r}^{n} C(i,r) = C(n+1, r+1)。
• 吸收恒等式：k·C(n,k) = n·C(n-1, k-1)。

常用数值

表达式	值
1/2	0.5
1/3	0.333...
1/7	0.142857142857...（循环节 6 位）
1/9	0.111...
√2	1.4142135...
√3	1.7320508...
√5	2.2360679...
e	2.7182818...
π	3.1415926...
ln 2	0.6931...
log₁₀ 2	0.3010
log₁₀ 3	0.4771
φ（黄金分割）	(1+√5)/2 ≈ 1.618

重要分解

• 1001 = 7 × 11 × 13
• 10⁶ - 1 = 999999 = 3³ × 7 × 11 × 13 × 37
• 2¹⁰ = 1024 ≈ 10³（"千字节"的由来）
• 2³² ≈ 4.29 × 10⁹
• 2⁶⁴ ≈ 1.84 × 10¹⁹

---

题目 1：1 到 100 求和（高斯法）

题面

快速计算 1+2+3+...+100 的值。

拆解与思考

高斯 7 岁时的方法：把数列正着写一遍，再倒着写一遍：

  1 +   2 +   3 + ... + 100
100 +  99 +  98 + ... +   1

上下对应相加：每一对都是 101，共 100 对：

2S = 100 × 101 = 10100
S = 5050

推广到任意等差数列：前 n 项和 = n × (首项 + 末项) / 2。

答案

1 + 2 + ... + 100 = 5050。一般公式：S = n(n+1)/2。

延伸：其他求和公式

平方和：

1² + 2² + ... + n² = n(n+1)(2n+1)/6

证明思路：利用 (k+1)³ - k³ = 3k² + 3k + 1，对 k 求和后消去立方项。

立方和：

1³ + 2³ + ... + n³ = [n(n+1)/2]²

注意：立方和等于和的平方——非常优美的恒等式。

n	1³+2³+...+n³	(1+2+...+n)²
1	1	1
2	9	9
3	36	36
4	100	100

几何级数：

1 + 2 + 4 + ... + 2ⁿ = 2ⁿ⁺¹ - 1（棋盘放麦子故事的来源）

调和级数发散：

1 + 1/2 + 1/3 + ... + 1/n → ∞（但发散极慢，H_n ≈ ln n）

工程意义

等差/等比数列求和是分析循环复杂度的基础。例如：

• 双重循环 for i, for j < i：总次数 1 + 2 + ... + n = O(n²)。
• 二分查找 n → n/2 → n/4 → ...：步数 O(log n)，因为 n/2 + n/4 + ... < n。

---

题目 2：整除判别法全集

题面

如何不实际做除法，判断一个数能否被 2、3、4、5、6、7、8、9、10、11、13 整除？

拆解与思考

基础判别法（必背）

除数	判别法	例
2	末位偶数	124 ÷ 2 ✓
3	数字和能被 3 整除	123 → 1+2+3=6 ✓
4	末两位能被 4 整除	1236 → 36 ÷ 4 ✓
5	末位 0 或 5	125 ✓
6	同时满足 2 和 3	132（偶 + 1+3+2=6）✓
8	末三位能被 8 整除	12344 → 344 ÷ 8 = 43 ✓
9	数字和能被 9 整除	1233 → 1+2+3+3=9 ✓
10	末位 0	1230 ✓

11 的判别法（经典）

奇位数字和 − 偶位数字和 能被 11 整除（含为 0）。

例：9247。

• 奇位和（第 1、3 位）= 9 + 4 = 13
• 偶位和（第 2、4 位）= 2 + 7 = 9
• 差 = 13 − 9 = 4，不能被 11 整除。

例：121。

• 奇位和 = 1 + 1 = 2，偶位和 = 2，差 = 0 ✓。

原理：10 ≡ -1 (mod 11)，所以 10ⁱ ≡ (-1)ⁱ (mod 11)。一个数 dₙ...d₂d₁d₀ mod 11 等于 d₀ - d₁ + d₂ - d₃ + ...。

7 和 13 的判别法（1001 法）

利用 1001 = 7 × 11 × 13。三位交替加减。

例：判断 142857 能否被 7 整除。分组：857 − 142 = 715。715 / 7 = 102.14，不能。但 715 / 11 = 65，715 / 13 = 55，所以 142857 能被 11 和 13 整除但不被 7 整除。

原理：10³ ≡ -1 (mod 1001)，所以 10³ⁱ ≡ (-1)ⁱ (mod 1001)，三位分组交替加减的结果 mod 1001 即原数 mod 1001。1001 = 7×11×13，所以这个结果也对 7、11、13 同余。

7 的另一种判别法

截尾法：去掉末位，剩下数减去末位的 2 倍，结果能被 7 整除则原数能。

例：343。剩下 34，末位 3，34 − 2×3 = 28，28 ÷ 7 ✓。

原理：设 N = 10a + b，则 N - 21b = 10a - 20b = 10(a - 2b)。21b 是 7 的倍数，所以 N mod 7 = 10(a - 2b) mod 7，等价于判断 a - 2b 能否被 7 整除。

答案

除数	判别法
7	截尾减 2 倍 / 三位交替加减
11	奇偶位数字和之差
13	三位交替加减

延伸

所有判别法都是模运算：n 能被 d 整除 ⇔ n ≡ 0 (mod d)。判别法只是简化 mod 计算的捷径。

工程意义：在大数处理、密码学、校验码（ISBN、信用卡号 Luhn 算法）中都有应用。

---

题目 3：快速平方（接近 100 的数）

题面

快速计算 97² 和 103²。

拆解与思考

方法 1：基于 100 的偏差

97²（97 比 100 少 3）：

1. 算偏差：97 − 3 = 94（这是结果的前两位）。
2. 偏差平方：3² = 09（必须补到两位）。
3. 拼接：94 | 09 = 9409。

原理：(100 − a)² = 10000 − 200a + a² = 100·(100 − 2a) + a² = 100·(97 − 3) + 9 = 9409。

103²（103 比 100 多 3）：

1. 103 + 3 = 106。
2. 3² = 09。
3. 拼接：106 | 09 = 10609。

答案

97² = 9409，103² = 10609。

延伸：推广到任意基底

接近 50：(50 ± a)² = 2500 ± 100a + a²。

例：52² = 2500 + 200 + 4 = 2704。

接近 1000：(1000 ± a)² = 10⁶ ± 2000a + a²，偏差平方需补到 3 位。

任意两位数平方（Yavadunam 法）：

例：43²。

• 偏离基数 50：43 - 50 = -7。
• 43 + (-7) = 36，结果前部分。
• (-7)² = 49，结果后部分（基底 50，补 2 位）。
• 拼接：36 | 49 = 1849？验算：43² = 1849 ✓。

但要注意：偏差结果超过基底会"溢出"，需进位。

速算其他技巧

11 倍速算（两位数）：

36 × 11：把 3 和 6 拆开，中间填 3 + 6 = 9，结果 396。

78 × 11：7 + 8 = 15，需进位：7 | 15 | 8 → 8 | 5 | 8 = 858。

5 倍速算：N × 5 = N × 10 / 2，把 N 乘 10 后除以 2 比直接乘 5 更快。

乘 25：N × 25 = N × 100 / 4。

乘 9：N × 9 = N × 10 − N。

---

题目 4：模运算性质

题面

证明：(a × b) mod n = ((a mod n) × (b mod n)) mod n。

拆解与思考

设 a = qn + r₁（0 ≤ r₁ < n），b = pn + r₂（0 ≤ r₂ < n）。则：

a × b = (qn + r₁)(pn + r₂)
      = qp·n² + qn·r₂ + pn·r₁ + r₁·r₂

前三项都含因子 n，故：

(a × b) mod n = (r₁ · r₂) mod n
             = ((a mod n) · (b mod n)) mod n

答案

证毕。核心直觉：模 n 运算下，乘法和加法可以"边算边取模"，不需要先算出大数再取模。

延伸：模运算全套性质

性质	公式
加法	(a + b) mod n = ((a mod n) + (b mod n)) mod n
减法	(a - b) mod n = ((a mod n) - (b mod n) + n) mod n
乘法	(a · b) mod n = ((a mod n) · (b mod n)) mod n
幂	aᵏ mod n 用快速幂计算

注意：除法不一定保持。ab mod n = ac mod n 不能推出 b ≡ c (mod n)，除非 gcd(a, n) = 1。

快速幂算法

计算 a^b mod n，朴素 O(b)，快速幂 O(log b)。

def fast_pow(a, b, n):
    result = 1
    a = a % n
    while b > 0:
        if b & 1:  # b 是奇数
            result = (result * a) % n
        b >>= 1
        a = (a * a) % n
    return result

原理：a^b = (a²)^(b/2)（b 偶），或 a · (a²)^((b-1)/2)（b 奇）。

工程意义

RSA 加密的核心操作就是 m^e mod n 和 c^d mod n。没有快速幂，2048 位 RSA 根本无法实现。

---

题目 5：辗转相除法求 GCD

题面

用辗转相除法求 gcd(252, 198)。

拆解与思考

辗转相除法的核心定理：gcd(a, b) = gcd(b, a mod b)，当余数为 0 时，除数即为 GCD。

为什么成立？设 d | a 且 d | b，则 d | (a - qb) = a mod b。反过来若 d | b 且 d | (a mod b)，则 d | (qb + (a mod b)) = a。所以 a, b 的公因数集合 = b, a mod b 的公因数集合，最大值相同。

逐步计算：

252 = 198 × 1 + 54  → gcd(252, 198) = gcd(198, 54)
198 =  54 × 3 + 36  → gcd(198, 54)  = gcd(54, 36)
 54 =  36 × 1 + 18  → gcd(54, 36)   = gcd(36, 18)
 36 =  18 × 2 + 0   → 余数为 0，停止

答案

gcd(252, 198) = 18。

复杂度分析

• 最坏情况：斐波那契数列相邻两项 gcd(F_{n+1}, F_n)，需要 n 步。
• 复杂度：O(log(min(a, b)))，由 Lamé 定理保证（1844 年）。

代码实现

# 迭代版
def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

# 递归版
def gcd_rec(a, b):
    return a if b == 0 else gcd_rec(b, a % b)

延伸：扩展欧几里得算法

贝祖定理：对任意整数 a、b，存在整数 x、y 使得 ax + by = gcd(a, b)。

扩展 GCD 算法在求 GCD 的同时返回 x、y：

def ext_gcd(a, b):
    if b == 0:
        return a, 1, 0
    g, x, y = ext_gcd(b, a % b)
    return g, y, x - (a // b) * y

应用：

• 求模逆元：a · x ≡ 1 (mod n)，用 ext_gcd 求 x。
• RSA 密钥生成：选 e 使 gcd(e, φ(n)) = 1，再用 ext_gcd 求 d 使 e · d ≡ 1 (mod φ(n))。
• 解线性 Diophantine 方程：ax + by = c。

---

题目 6：中国剩余定理（CRT）

题面

一个数除以 3 余 1，除以 5 余 2，除以 7 余 4。求满足条件的最小正整数。

拆解与思考

中国剩余定理（CRT）：若模数 m₁, m₂, ..., mₖ 两两互质，则同余方程组在模 M = m₁·m₂·...·mₖ 范围内有唯一解。

3、5、7 两两互质，M = 105。

构造解：

设 x ≡ 1 (mod 3)，x ≡ 2 (mod 5)，x ≡ 4 (mod 7)。

1. 令 Mᵢ = M / mᵢ：

   • M₁ = 105/3 = 35
   • M₂ = 105/5 = 21
   • M₃ = 105/7 = 15

2. 找 yᵢ 使 Mᵢ · yᵢ ≡ 1 (mod mᵢ)（即 Mᵢ 模 mᵢ 的逆）：

   • 35 · y₁ ≡ 2·y₁ ≡ 1 (mod 3)，y₁ = 2（2·2=4≡1）。
   • 21 · y₂ ≡ 1·y₂ ≡ 1 (mod 5)，y₂ = 1。
   • 15 · y₃ ≡ 1·y₃ ≡ 1 (mod 7)，y₃ = 1。

3. 解：x = Σ rᵢ · Mᵢ · yᵢ (mod M)：

   • x = 1·35·2 + 2·21·1 + 4·15·1 = 70 + 42 + 60 = 172
   • x mod 105 = 172 − 105 = 67

验证：67/3=22...1 ✓，67/5=13...2 ✓，67/7=9...4 ✓。

答案

最小正整数解是 67。

历史背景

《孙子算经》（约公元 3-5 世纪）原题："今有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二，问物几何？"答案是 23。

CRT 在西方由 Gauss 在《算术研究》（1801）中独立重述。

工程意义

RSA 解密加速：模 N = p·q 的运算可拆成模 p 和模 q 两个小运算，由 CRT 合并。速度提升约 4 倍（因为模数位宽减半）。

并行计算：大数运算可拆到多个互质模数上并行执行，最后合并结果。

---

题目 7：帕斯卡三角与二项式系数

题面

利用帕斯卡三角计算 C(6,2) 并解释三角形的结构。

拆解与思考

帕斯卡三角的第 n 行（从第 0 行开始）给出 C(n,k)（k = 0, 1, ..., n）：

第0行:              1
第1行:             1 1
第2行:            1 2 1
第3行:           1 3 3 1
第4行:          1 4 6 4 1
第5行:        1 5 10 10 5 1
第6行:      1 6 15 20 15 6 1

递推关系：C(n,k) = C(n-1,k-1) + C(n-1,k)，边界 C(n,0) = C(n,n) = 1。

直观理解：从 n 个中选 k 个，要么选第 n 个（剩 n−1 选 k−1），要么不选（剩 n−1 选 k）。

从第 6 行直接读：C(6,0)=1, C(6,1)=6, C(6,2)=15, C(6,3)=20, ...。

答案

C(6,2) = 15。

帕斯卡三角的宝藏

性质	描述
第 n 行和	2ⁿ（二项式定理取 a=b=1）
对角线和	斜对角线元素和 = 斐波那契数
Hockey Stick	沿一列累加到右下 = 右下的下一格
Sierpinski 三角	奇数位置形成的分形结构
二项分布	行归一化即为概率分布
卡塔兰数	中间列的特殊组合

二项式定理

$(a+b)^n = \sum_{k=0}^{n} C(n,k) a^{n-k} b^k$

经典应用：

• (1+1)ⁿ = 2ⁿ = Σ C(n,k)。
• (1-1)ⁿ = 0 = Σ (-1)ᵏ C(n,k)（n ≥ 1）。
• (a+b)² = a² + 2ab + b²。
• (x+y)³ = x³ + 3x²y + 3xy² + y³。

多项式系数

C(n, k₁, k₂, ..., k_m)（k₁ + k₂ + ... + k_m = n）是多项式 (x₁ + x₂ + ... + x_m)ⁿ 展开中 x₁^{k₁} x₂^{k₂} ... x_m^{k_m} 的系数，等于 n! / (k₁! k₂! ... k_m!)。

---

题目 8：握手定理

题面

一次聚会有 n 个人，证明：握过奇数次手的人数一定是偶数。

拆解与思考

将人视为图的顶点，握手视为边。每个顶点的度数 = 该人的握手次数。

关键观察：所有顶点度数之和 = 2 × 边数（因为每条边贡献两个端点各 1 度）。

所以度数总和恒为偶数。

而偶数 = 偶数个奇数之和 + 任意个偶数之和。因此奇数度顶点的个数必须是偶数。

答案

证毕。握手总次数 = 2 × 握手对数，所以度数和恒为偶数，奇度点个数必为偶数。

推论

• 在任何社交网络中，拥有奇数个好友的人一定是偶数个。
• 不存在每个顶点度数都为奇数且有奇数个顶点的图。
• n 阶完全图 K_n 的边数为 n(n-1)/2（每个顶点度数 n-1，握手定理验证：n(n-1)/2 是整数要求 n 或 n-1 中至少一个偶数——总是成立）。

延伸：图论基础定理

定理	内容
握手引理	度数和 = 2·边数
欧拉公式	平面图：V − E + F = 2
完全图边数	C(n, 2) = n(n-1)/2
二分图判定	不含奇环 ⇔ 2-可着色
七桥问题	欧拉回路 ⇔ 所有顶点度数为偶

---

题目 9：斐波那契数列

题面

斐波那契数列 F(0)=0, F(1)=1, F(n)=F(n-1)+F(n-2)。求通项公式。

拆解与思考

Binet 公式（通项）：

$F(n) = \frac{1}{\sqrt{5}} \left[ \left(\frac{1+\sqrt{5}}{2}\right)^n - \left(\frac{1-\sqrt{5}}{2}\right)^n \right]$

推导：解特征方程 x² = x + 1，两根 φ = (1+√5)/2 ≈ 1.618 和 ψ = (1-√5)/2 ≈ -0.618。通解 F(n) = A·φⁿ + B·ψⁿ，代入 F(0)=0, F(1)=1 解出 A、B。

关键性质

性质	公式
Cassini 恒等式	F(n+1)·F(n-1) − F(n)² = (−1)ⁿ
前缀和	F(0) + F(1) + ... + F(n) = F(n+2) − 1
平方和	F(1)² + F(2)² + ... + F(n)² = F(n)·F(n+1)
与卢卡斯数	L(n) = F(n-1) + F(n+1)
GCD 性质	gcd(F(m), F(n)) = F(gcd(m, n))

黄金分割的联系

F(n+1)/F(n) → φ = (1+√5)/2 ≈ 1.618。

n	F(n)	F(n+1)/F(n)
1	1	1.000
5	5	1.667
10	55	1.618
15	610	1.618

工程意义：黄金分割比在艺术、建筑、自然（向日葵种子、贝壳螺旋）中普遍出现。

算法：求 F(n) 的最快方法

朴素递归：O(2ⁿ)（爆炸）。 动态规划：O(n)。 矩阵快速幂：O(log n)。

$\begin{pmatrix} F(n+1) \\ F(n) \end{pmatrix} = \begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix}^n \begin{pmatrix} 1 \\ 0 \end{pmatrix}$

def fib(n):
    def mat_mul(A, B):
        return [[A[0][0]*B[0][0]+A[0][1]*B[1][0], A[0][0]*B[0][1]+A[0][1]*B[1][1]],
                [A[1][0]*B[0][0]+A[1][1]*B[1][0], A[1][0]*B[0][1]+A[1][1]*B[1][1]]]
    def mat_pow(M, k):
        R = [[1,0],[0,1]]
        while k:
            if k & 1: R = mat_mul(R, M)
            M = mat_mul(M, M)
            k >>= 1
        return R
    return mat_pow([[1,1],[1,0]], n)[0][1]

---

题目 10：卡塔兰数

题面

n 对括号有多少种合法匹配方式？（如 n=3：((())), (()()), (())(), ()(()), ()()() 共 5 种）

拆解与思考

答案是第 n 个卡塔兰数：

$C_n = \frac{1}{n+1} \binom{2n}{n} = \frac{(2n)!}{(n+1)! \cdot n!}$

n	Cₙ	含义
0	1	空括号
1	1	()
2	2	()() , (())
3	5	5 种括号匹配
4	14	4 对括号
5	42
10	16796
15	9694845

递推公式

$C_0 = 1, \quad C_{n+1} = \sum_{i=0}^{n} C_i \cdot C_{n-i}$

或等价地 C_{n+1} = (2(2n+1)/(n+2)) · C_n。

卡塔兰数的应用场景

C_n 计数很多看似不相关的对象：

场景	解释
n 对括号合法匹配	必须前缀中 ( 数 ≥ ) 数
n+1 个叶子二叉树的形态数	根分左右子树，递归
凸 (n+2) 边形的三角剖分数	选一条边，递归分两侧
n 个元素的合法出栈序列	入栈 1..n，出栈顺序
不越过对角线的网格路径	从 (0,0) 到 (n,n) 不跨 y=x
圆上 2n 个点的非交叉弦	任选一点连弦，递归

巧妙证明（反射原理）

合法括号数 = 总排列数 − 非法排列数。

• 总排列数：C(2n, n)。
• 非法数：第一个非法时刻（右括号比左括号多 1）后，翻转后续所有括号，得到 n+1 个左、n−1 个右的排列。此映射是双射。
• 非法数 = C(2n, n+1) = C(2n, n−1)。

合法数 = C(2n, n) − C(2n, n−1) = C(2n,n)/(n+1) = Cₙ。

---

题目 11：整数拆分最大乘积

题面

把整数 n 拆成若干正整数之和，使它们的乘积最大。如 10 = 3+3+4，乘积 3·3·4 = 36。求一般解法。

拆解与思考

设拆分为 a₁, a₂, ..., aₖ（和为 n），最大化 a₁·a₂·...·aₖ。

关键观察：

• 不应有 1（1 不增益乘积）。
• 不应有 ≥ 5 的数（拆成 3 和 a-3 乘积更大，因为 3(a-3) > a 当 a > 4.5）。
• 4 应拆成 2+2（2·2 = 4 不变，可统一为 2）。
• 不应有 3 个 2（2+2+2 = 6，但 3+3 = 6，3·3 > 2·2·2）。

最优策略：尽可能多用 3，剩余用 2 补。

设 n = 3q + r：

• r = 0：拆成 q 个 3，乘积 3^q。
• r = 1：把一个 3 和这个 1 合并成 2+2，乘积 3^(q-1) · 4。
• r = 2：拆成 q 个 3 加一个 2，乘积 3^q · 2。

答案

def max_product(n):
    if n <= 3: return n - 1  # 特殊：2->1, 3->2
    q, r = divmod(n, 3)
    if r == 0: return 3 ** q
    if r == 1: return 3 ** (q - 1) * 4
    return 3 ** q * 2

延伸：与 e 的联系

把 n 拆成等份，每份大小 n/k，乘积 (n/k)^k。最大化 ln((n/k)^k) = k ln(n/k)。

对 k 求导：d/dk [k ln(n/k)] = ln(n/k) - 1，令其为 0：n/k = e。

所以最优份数大小是 e ≈ 2.718，整数最近的就是 3。这就是为什么应该多用 3。

工程意义

LeetCode 343 整数拆分。本质是贪心策略 + 数学优化的典型。

---

题目 12：牛顿迭代法

题面

不用库函数，如何快速求 √2 的近似值？

拆解与思考

牛顿迭代法：求方程 f(x) = 0 的根。

迭代公式：x_{n+1} = x_n - f(x_n) / f'(x_n)。

几何意义：在当前点作切线，与 x 轴交点作为下一个近似值。

求 √2：解 x² = 2，即 f(x) = x² - 2。f'(x) = 2x。

迭代：x_{n+1} = x_n - (x_n² - 2)/(2x_n) = (x_n + 2/x_n) / 2。

取 x₀ = 1：

n	xₙ
0	1
1	1.5
2	1.4167
3	1.414216
4	1.414213562...

4 步就达到 1.414213562 的精度。平方收敛（每步有效位数翻倍）。

推广

求 √a：x_{n+1} = (x_n + a/x_n) / 2。

求 c 的立方根：解 x³ - c = 0，x_{n+1} = (2x_n + c/x_n²) / 3。

除法变乘法（CPU 用）：求 1/a，解 1/x - a = 0，x_{n+1} = x_n(2 - a·x_n)。

def sqrt_newton(a, eps=1e-10):
    if a < 0: raise ValueError
    if a == 0: return 0
    x = a
    while abs(x * x - a) > eps:
        x = (x + a / x) / 2
    return x

工程意义

• CPU 浮点除法和开方都用牛顿法或其改进版（如 Goldschmidt）。
• 机器学习优化：牛顿法是二阶优化，比梯度下降收敛更快但计算 Hessian 昂贵。
• 方程求根：物理仿真、金融定价中的隐式方程求解。

---

题目 13：蓄水池抽样

题面

一个数据流长度未知（可能极长甚至无限），要求等概率随机抽出 1 个元素。空间 O(1)。

拆解与思考

蓄水池抽样算法（R-1）：

保留第 1 个元素
对第 i 个元素（i ≥ 2）：以 1/i 的概率替换保留的元素

正确性证明：第 i 个元素最终被保留的概率：

P(i 最终保留) = P(第 i 步选中) · P(后续所有步都不替换)

• P(第 i 步选中) = 1/i
• P(后续第 j 步不替换)（j > i）= 1 - 1/j = (j-1)/j

所以：

$P(i) = \frac{1}{i} \cdot \frac{i}{i+1} \cdot \frac{i+1}{i+2} \cdots \frac{n-1}{n} = \frac{1}{n}$

完美——每个元素被选中的概率都是 1/n。

推广：抽 k 个元素

前 k 个元素入蓄水池
对第 i 个元素（i > k）：以 k/i 的概率选中；若选中，随机替换池中一个

每个元素被选中的概率均为 k/n。

import random
def reservoir_sample(stream, k):
    pool = []
    for i, item in enumerate(stream):
        if i < k:
            pool.append(item)
        else:
            j = random.randint(0, i)
            if j < k:
                pool[j] = item
    return pool

工程意义

• 大数据流采样：日志分析、监控指标抽样。
• 随机化算法：随机化快排、MinHash。
• 在线算法：单遍扫描，O(1) 空间。

---

题目 14：经典不等式速查

题面

列出面试中常用的不等式。

常用不等式

AM-GM 不等式（算术平均 ≥ 几何平均）：

$\frac{a_1 + a_2 + \cdots + a_n}{n} \geq \sqrt[n]{a_1 a_2 \cdots a_n}$

等号当且仅当所有 aᵢ 相等。

应用：周长固定，正方形面积最大；表面积固定，球体积最大。

柯西-施瓦茨不等式：

$(a_1 b_1 + a_2 b_2 + \cdots + a_n b_n)^2 \leq (a_1^2 + \cdots + a_n^2)(b_1^2 + \cdots + b_n^2)$

杨不等式：

$\left(\sum a_i b_i\right)^2 \leq \left(\sum a_i^2\right)\left(\sum b_i^2\right)$

（柯西-施瓦茨的等价形式。）

三角形不等式：

$|a + b| \leq |a| + |b|$

幂平均不等式：对 r > s：

$\left(\frac{\sum a_i^r}{n}\right)^{1/r} \geq \left(\frac{\sum a_i^s}{n}\right)^{1/s}$

伯努利不等式：对 x > -1，n ≥ 1：

$(1 + x)^n \geq 1 + nx$

Jensen 不等式：凸函数 f：

$f\left(\frac{\sum a_i}{n}\right) \leq \frac{\sum f(a_i)}{n}$

应用例子

1. 周长固定的矩形，正方形面积最大：设长 a 宽 b，a + b = L。ab ≤ ((a+b)/2)² = L²/4。

2. n 个正数之和固定，相等时乘积最大：a + b + ... = S，乘积最大在所有 aᵢ 相等。

3. 容斥原理的应用：|A ∪ B| = |A| + |B| − |A ∩ B|。

---

题目 15：圆周率的几种算法

题面

不用 π 库函数，编程计算 π 的近似值。

方法 1：蒙特卡洛

随机投点 (x, y) ∈ [0,1]²，落入单位圆内的概率 π/4。

import random
def pi_mc(n=1000000):
    inside = 0
    for _ in range(n):
        if random.random()**2 + random.random()**2 < 1:
            inside += 1
    return 4 * inside / n

收敛慢：O(1/√n)。

方法 2：莱布尼茨级数

$\frac{\pi}{4} = 1 - \frac{1}{3} + \frac{1}{5} - \frac{1}{7} + \cdots$

收敛极慢（要 10ⁿ 项才有 n 位精度）。

方法 3：马钦公式

$\frac{\pi}{4} = 4 \arctan\frac{1}{5} - \arctan\frac{1}{239}$

配合泰勒展开 arctan(x) = x - x³/3 + x⁵/5 - ...，收敛快。

方法 4：Chudnovsky 算法（实战最快）

$\frac{1}{\pi} = 12 \sum_{k=0}^{\infty} \frac{(-1)^k (6k)! (13591409 + 545140134k)}{(3k)! (k!)^3 640320^{3k+3/2}}$

每项给约 14 位有效数字。圆周率世界纪录（数十万亿位）都用此算法。

方法 5：BBP 公式（直接算第 n 位）

$\pi = \sum_{k=0}^{\infty} \frac{1}{16^k} \left( \frac{4}{8k+1} - \frac{2}{8k+4} - \frac{1}{8k+5} - \frac{1}{8k+6} \right)$

特点：能直接算 π 的第 n 位十六进制小数，不需算前面所有位。

工程意义

数值计算、伪随机数生成、信号处理（FFT 角度参数）都用到 π。

---

题目 16：圆上点的距离期望

题面

圆上有 n 个点，求它们两两距离之和的期望（点等概率独立均匀分布）。

拆解与思考

期望线性性：距离总和 = C(n, 2) 对距离之和，每对距离期望相同，所以：

E[总距离] = C(n, 2) · E[两点距离]

两点距离：圆周长归一化为 1，两点的"顺时针弧长" U 均匀分布 [0, 1]，最短距离 min(U, 1-U)。

$E[d] = \int_0^1 \min(u, 1-u) \cdot 1 \, du = 2 \int_0^{1/2} u \, du = 2 \cdot \frac{(1/2)^2}{2} = \frac{1}{4}$

所以 E[总距离] = C(n, 2) · 1/4 = n(n-1)/8。

答案

期望距离之和 = n(n-1)/8（圆周长归一化为 1）。

延伸

期望线性性是处理复杂问题的利器：把"n 个变量的复杂函数"分解为"成对贡献之和"，每对独立分析。

工程意义：哈希冲突分析、随机化算法的平均复杂度都用类似技巧。

---

解题模板（总结）

通用流程

1. 寻找对称性——配对、首尾相加、镜像。
2. 利用特殊数的性质——1001 = 7×11×13，10^k ≡ 1 (mod 9) 等。
3. 边算边取模——避免大数运算。
4. 递推思想——GCD、CRT、动态规划都源于此。
5. 归纳与递归——帕斯卡、斐波那契、卡塔兰数。
6. 组合恒等式简化计数问题。
7. 期望线性性——拆复杂期望为简单期望之和。
8. 图论不变量——度数和、欧拉公式。

信号清单

题面信号	推理工具
"等差/等比数列求和"	高斯配对法 / 求和公式
"判断整除"	数字和 / 三位交替 / 截尾法
"快速计算 a²"	偏差法（基底 100 或 50）
"大数模运算"	边算边取模 / 快速幂
"求 gcd / 逆元"	辗转相除 / 扩展欧几里得
"同余方程组"	中国剩余定理
"组合计数"	帕斯卡三角 / 卡塔兰数
"随机选择 / 数据流"	蓄水池抽样
"求根 / 最优化"	牛顿迭代
"整数拆分最值"	多用 3（贪心 + 数学）

常见陷阱

• 等比求和忘 r=1：当 r=1 时不能用 a(1-rⁿ)/(1-r)，应直接 na。
• 模运算中的除法：不能简单"模除"，要用逆元或贝祖定理。
• 整数溢出：组合数 C(100, 50) 远超 int64，必须边乘边除或用大整数。
• 归纳基例：n=0、n=1 都要单独验证。
• 贪心策略不证明：整数拆分"多用 3"需要严谨证明，否则可能反例。

延伸阅读

书籍

• 《数论导引》— Hardy & Wright，经典数论教材
• 《具体数学》— Graham, Knuth, Patashnik，计算机科学必备数学
• 《数学桥》— Stephen Fletcher Hewson，高等数学入门
• 《数学女孩》— 结城浩，趣味数学小说
• 《Proofs from THE BOOK》— Aigner & Ziegler，数学之美展示

在线资源

• 帕斯卡三角的奥秘
• OEIS 整数序列百科 — 任何数列都能查到
• Project Euler — 数学编程题
• Brilliant - Number Theory
• Vedic Mathematics — 印度速算体系