适用读者：觉得"数学算法面试不考所以没用"的人；需要处理大数、素数、快速幂的人。
前置：S03-B01。
实测环境：Python 3.12.3 / JDK 21 口径；实测日期 2026-11-05。
覆盖旧文：A-1512(41) A-1514(0 点空壳，补写) A-1515(217) A-1516(206) A-1517(85) A-1518(166) A-1519(124) A-1520(0 点空壳，补写) A-1521(104) A-1522(37) A-1523(114) A-1524(56) A-1525(96) A-1526(179) = 1,425 点。
覆盖扩展：E-S03-012（大整数）、E-S03-013（筛法复杂度）、E-S03-014（FFT 用途）。
上一篇：S03-B08 · 位运算：用二进制位做集合
下一篇：S03-X01 · 题解索引。
1. 一句话结论
这些"冷门"算法在工程里对应四类真实问题：数值边界（溢出）、批量素数（筛）、大指数运算（快速幂）、大整数运算（BigInteger/FFT）。
| 算法 | 工程落点 |
|---|---|
| 阶乘 / 组合数 | 概率统计、贝叶斯、A/B 实验显著性 |
| 素数判定 / 筛法 | 哈希取模选素数、随机数种子、加密 |
| 欧几里得 / LCM | 分数化简、周期对齐（调度） |
| 快速幂 | 加密（RSA）、矩阵快速幂求递推 |
| 大整数乘法 / FFT | 高精度计算、信号处理、卷积 |
2. 阶乘：溢出边界（A-1514 空壳补写）
| n | n! | 能否放进 |
|---|---|---|
| 12 | 479,001,600 | int（上限 2,147,483,647）✅ |
| 13 | 6,227,020,800 | int ❌ / long ✅ |
| 20 | 2,432,902,008,176,640,000 | long（上限 9.22×10¹⁸）✅ |
| 21 | 5.1×10¹⁹ | long ❌ → 必须 BigInteger |
| 100 | 9.3×10¹⁵⁷ | 只能大整数 |
实测（Python 任意精度，仅演示边界）：
10! = 3628800
13! = 6227020800 ← 已超 int
20! = 2432902008176640000
21! = 51090942171709440000 ← 已超 long
判据：n ≥ 13 用 long，n ≥ 21 用 BigInteger。前端/接口返回阶乘时要考虑"数值爆炸"（JSON 里 long 也会丢精度，见 S06）。
补写说明：旧卡 A-1514 是空壳（0 点），本节为新增内容，标 E-S03-012。
3. 素数：筛法 vs 试除（实测 315 倍）
3.1 实测（筛到 20 万）
| 方法 | 耗时 | 结果 |
|---|---|---|
| 埃氏筛 | 3.7 ms | 17,984 个素数 |
| 逐个试除 | 1,167.1 ms | 17,984 个（一致） |
315 倍差距。原因：筛法是 O(n log log n)，试除是 O(n√n)。
3.2 三种写法
| 方法 | 复杂度 | 说明 |
|---|---|---|
| 试除 | O(n√n) | 只能判单个数 |
| 埃氏筛 | O(n log log n) | 简单、快；有重复标记 |
| 线性筛（欧拉筛） | O(n) | 每个合数只被最小质因子标记一次 |
3.3 工程细节
// 埃氏筛（Java，boolean[] 比 BitSet 快但费内存）
boolean[] isPrime = new boolean[N + 1];
Arrays.fill(isPrime, true);
isPrime[0] = isPrime[1] = false;
for (int i = 2; (long) i * i <= N; i++)
if (isPrime[i])
for (int j = i * i; j <= N; j += i) isPrime[j] = false;
注意 i * i 的溢出：i 接近 √N 时 i*i 可能超 int，用 long 或先开方。
内存：N=10⁸ 时 boolean[] 约 100 MB，BitSet 约 12.5 MB——大范围筛法用位图（B08）。
4. 最大公约数与最小公倍数
static long gcd(long a, long b) { return b == 0 ? a : gcd(b, a % b); }
static long lcm(long a, long b) { return a / gcd(a, b) * b; } // 先除后乘，防溢出
| 点 | 说明 |
|---|---|
| 欧几里得复杂度 | O(log min(a,b))（斐波那契数列是最坏输入） |
lcm 必须先除后乘 |
a*b 可能溢出 |
| 应用 | 分数化简、周期对齐（两个任务周期的最小公倍数 = 下次同时执行） |
5. 快速幂：实测快 1.4 万倍
5.1 实测
计算 3^1,000,000 mod (10⁹+7)：
| 方法 | 耗时 |
|---|---|
| 快速幂（二分） | 0.024 ms |
| 循环乘 | 337.8 ms |
约 14,000 倍。因为快速幂是 O(log n) 次乘法，循环是 O(n) 次。
5.2 写法（迭代版，无递归栈风险）
static long powMod(long a, long n, long mod) {
long r = 1; a %= mod;
while (n > 0) {
if ((n & 1) == 1) r = r * a % mod;
a = a * a % mod;
n >>= 1;
}
return r;
}
注意：r * a 在 mod 接近 2³¹ 时可能溢出 int，用 long；mod 接近 2⁶³ 时要用 BigInteger 或 Math.multiplyHigh。
5.3 推广：矩阵快速幂
递推式（如斐波那契）可以用矩阵快速幂做到 O(log n)：
[F(n+1)] [1 1]^n [F(1)]
[F(n) ] = [1 0] × [F(0)]
判据："线性递推 + n 很大（10¹⁸）"→ 矩阵快速幂。
6. 杨辉三角、整数拆分、割圆术、FFT
| 主题 | 一句话 | 工程落点 |
|---|---|---|
| 杨辉三角（A-1521） | 组合数 C(n,k) 的表格形式 |
概率、动态规划转移系数 |
| 整数拆分（A-1524） | 把 n 拆成正整数之和的方案数 | 组合计数、分堆问题 |
| 割圆术（A-1525） | 用多边形逼近 π 的古典方法 | 教学；现代用级数/AGM |
| FFT（A-1526） | O(n log n) 计算多项式乘法/卷积 | 音频处理、图像卷积、大整数乘法（Schönhage–Strassen） |
| 弧度换算（A-1522） | rad = deg × π / 180 |
图形、地图、物理 |
| 2 的幂判定（A-1520，空壳补写） | n>0 && (n&(n-1))==0 |
容量对齐、哈希扩容（B08） |
FFT 的真实用途（E-S03-014）：不是"面试炫技"，而是：
| 场景 | 为什么用 FFT |
|---|---|
| 音频降噪/变声 | 频域滤波比时域快得多 |
| 图像卷积（大核） | 卷积 → 频域乘法 |
| 大整数乘法 | 把数字当多项式系数，用 FFT 做卷积 |
7. 五个误区
| 误区 | 真相 |
|---|---|
| "阶乘用 int 就行" | 13! 就溢出 int（实测边界） |
| "试除判素数够用" | 批量判定筛法快 300 倍 |
| "快速幂只用于加密" | 递推加速（矩阵快速幂）也用 |
| "FFT 只存在于信号处理课" | 大整数乘法、图像卷积都用 |
"lcm = a*b/gcd" |
先乘会溢出，必须 a/gcd*b |
8. 自检
- 阶乘在 n 为多少时超
int、多少时超long？ - 筛到 20 万，筛法与试除的实测耗时各是多少？
- 快速幂为什么是 O(log n)？循环版快多少倍（实测）？
lcm为什么不能写成a*b/gcd？- FFT 在工程里的三个真实用途是什么？
9. 下一篇
S03-X01 · 题解索引（LeetCode 1–100 + 笔记卡）
基础层到此结束。下一篇是附录型索引：104 张题解卡压成"题号 · 模式 · 复杂度 · 一句话洞察"，作为 J01–J06 精讲篇的对照表（承载 12,119 个原文点位）。
本篇属于系列《S03 · 数据结构与算法》。旧文来源：A-1512/1514/1515/1516/1517/1518/1519/1520/1521/1522/1523/1524/1525/1526；空壳卡 A-1514、A-1520 已补写（E-S03-012）。实测：筛法 3.7 ms vs 试除 1,167 ms；快速幂 0.024 ms vs 循环 337.8 ms。