S03-X05 · 经典算法练习：LCM、素数筛与杨辉三角

lcm(a, b) 写成 a * b / gcd(a, b)，当 a = b = 100000 时结果是负数——不报错，小数据上永远正确。这三个入门题各自代表一类工程缺陷：边界缺失、下标混乱、中间量溢出。

1. GCD 与 LCM：先除后乘是硬性要求

public final class MathBasics {

    /* 递归版：语义贴合定义；深度与输入相关，典型量级是对数级 */
    static int gcdRec(int a, int b) {
        return b == 0 ? Math.abs(a) : gcdRec(b, a % b);
    }

    /* 迭代版：生产首选，无栈风险，入口统一处理负数 */
    static int gcd(int a, int b) {
        a = Math.abs(a);
        b = Math.abs(b);
        while (b != 0) {
            int t = a % b;
            a = b;
            b = t;
        }
        return a;                       // gcd(0,0) 返回 0，语义交给调用方
    }
}

递归的风险在深度：gcd(F(n), F(n-1)) 每轮只缩小一个斐波那契项，深度接近 n。int 下约 45 层、安全；真正的坑是负数——-7 % 3 是 -1，不取绝对值会一路传负数。

/* 错误写法：a * b 先算，中间量爆 int */
static int lcmBad(int a, int b) {
    return a * b / gcd(a, b);           // 100000 * 100000 已经溢出
}

/* 正确写法一：先除后乘，中间量不超过最终结果 */
static long lcm(long a, long b) {
    if (a == 0 || b == 0) return 0;     // 0 的倍数定义为 0
    long g = gcd((int) Math.abs(a), (int) Math.abs(b));
    return Math.abs(a / g * b);         // 先除再乘
}

/* 正确写法二：用 multiplyExact 把溢出变成异常 */
static int lcmExact(int a, int b) {
    if (a == 0 || b == 0) return 0;
    int g = gcd(a, b);
    return Math.multiplyExact(Math.abs(a / g), Math.abs(b));
}

a / g * b 中 g 整除 a，除法精确，中间值上界就是结果；a * b / g 的中间量是 a * b，可能比结果大 g 倍。这不是"可能溢出"，是必然溢出，只是阈值高低。

输入	`gcd`	`lcm`	说明
`(0, 0)`	`0`	`0`	数学未定义，工程上返回 0
`(0, 5)`	`5`	`0`	`gcd(0, a) = a` 是不变式
`(1, 1)`	`1`	`1`	最小用例
`(-7, 21)`	`7`	`21`	负数先取绝对值
`(MIN_VALUE, 1)`	溢出	溢出	`Math.abs(MIN_VALUE)` 仍是负数

最后一行是补码死角：MIN_VALUE 的绝对值超出 int 上界。处理办法只有两个——提升到 long，或显式拒绝该输入。

2. 素数筛：三档实现与各自适用面

static boolean isPrime(int n) {
    if (n < 2) return false;                       // 0、1、负数都不是质数
    if (n % 2 == 0) return n == 2;                 // 摘掉偶数后步长走 2
    for (int i = 3; (long) i * i <= n; i += 2) {
        if (n % i == 0) return false;
    }
    return true;
}

循环条件用 (long) i * i <= n 而非 i <= Math.sqrt(n)：后者返回 double，大整数边界可能差一次；而 i * i 在 i 接近 46341 时溢出 int，必须先转 long。

static boolean[] sieveEratosthenes(int n) {        // 返回 [0, n] 的标记数组
    boolean[] isComposite = new boolean[n + 1];
    isComposite[0] = true;
    if (n >= 1) isComposite[1] = true;             // 下标从 2 开始才有意义
    for (int i = 2; (long) i * i <= n; i++) {
        if (isComposite[i]) continue;
        for (long j = (long) i * i; j <= n; j += i) {   // j 用 long 防溢出
            isComposite[(int) j] = true;
        }
    }
    return isComposite;
}

从 i * i 开始标记：更小的倍数必然已被更小因子筛掉，这一步只减少重复写入，不改变 O(n log log n)。该量级的直觉是外层枚举质数 p、各标记 n/p 次，合计约 n · log log n——按素数定理推的结论，不是实测。

static List<Integer> sieveLinear(int n) {
    boolean[] isComposite = new boolean[n + 1];
    List<Integer> primes = new ArrayList<>();
    for (int i = 2; i <= n; i++) {
        if (!isComposite[i]) primes.add(i);
        for (int p : primes) {
            if ((long) p * i > n) break;
            isComposite[p * i] = true;
            if (i % p == 0) break;                 // 保证只用最小质因子筛一次
        }
    }
    return primes;
}

if (i % p == 0) break; 是线性筛的全部难点：保证每个合数只被最小质因子标记一次，总代价 O(n)。代价是维护 primes 列表且更难读；只判定不分解时埃氏筛更划算。

实现	时间	空间	额外产物	适合场景
单点试除	`O(sqrt(n))`	`O(1)`	无	少量大数判定
埃氏筛	`O(n log log n)`	`O(n)` 字节	判定标记	区间内全部质数
线性筛	`O(n)`	`O(n)` + 质数表	最小质因子、质数表	质因数分解、欧拉函数

3. 杨辉三角：滚动数组与组合数公式

static List<List<Integer>> pascalByRolling(int rows) {
    List<List<Integer>> res = new ArrayList<>();
    long[] cur = new long[rows];            // rows 较小时才成立
    for (int i = 0; i < rows; i++) {
        cur[i] = 1;                         // 行首
        for (int j = i - 1; j >= 1; j--) {  // 必须从右往左
            cur[j] = cur[j] + cur[j - 1];
        }
        List<Integer> row = new ArrayList<>(i + 1);
        for (int j = 0; j <= i; j++) row.add((int) cur[j]);
        res.add(row);
    }
    return res;
}

倒序是滚动数组的通用规则：cur[j] 依赖上一行的 cur[j] 与 cur[j-1]，从左往右时 cur[j-1] 已成本行值，结果全变成 2 的幂。这与 0-1 背包必须逆序同理。

组合数走递推式 C(n,k) = C(n-1,k-1) + C(n-1,k) 时只需 O(k) 的 long[]，内层同样必须从右往左（c[j] += c[j-1]），否则退化成二项式展开的重复累加。

方案	空间	支持取模	溢出边界	备注
滚动数组整行	`O(rows)`	视实现	`int` 行内求和即爆	适合小规模打印
组合数递推	`O(k)`	支持（加法取模）	`long` 约第 66 行	单点查询最优
阶乘 + 逆元	`O(n)` 预处理	要求模为质数	模意义下无溢出	大量查询
`BigInteger`	与位数相关	不需要	无	结果极大时唯一选择

long 上界 9.22e18，C(66, 33) 已接近该量级，第 66 行附近必然溢出——实现必须先回答"超界怎么办"：抛异常、取模，还是转 BigInteger。

4. 三个例子的共同点

维度	GCD/LCM	素数筛	杨辉三角
最小边界	`(0,0)`、`MIN_VALUE`	`n < 2`、`n = 0`	第 0 行、`rows = 0`
主要溢出点	`a * b`	`i * i`、`j += i`	`cur[j] + cur[j-1]`
下标陷阱	无	从 0 还是 2 开始	`j <= i` 的行列关系
可断言不变式	`gcd * lcm == a * b`（`long`）	每个合数恰有一个最小质因子	每行和为 `2^i`、两端为 1

正确性由边界和不变式保证，不由示例数据保证：lcm 的错误写法在 (4, 6) 下也返回 12，只有断言 gcd * lcm == a * b 才抓得到溢出。

5. 把练习脚本工程化

record Case(int a, int b, int expectGcd, long expectLcm) {}

static void check(boolean ok, String msg) {
    if (!ok) throw new AssertionError(msg);
}

static void runGcdCases() {
    List<Case> cases = List.of(
        new Case(0, 0, 0, 0), new Case(0, 5, 5, 0),
        new Case(4, 6, 2, 12), new Case(-7, 21, 7, 21),
        new Case(1_000_000, 999_983, 1, 999_983_000_000L));
    for (Case c : cases) {
        check(MathBasics.gcd(c.a(), c.b()) == c.expectGcd(), "gcd: " + c);
        check(MathBasics.lcm(c.a(), c.b()) == c.expectLcm(), "lcm: " + c);
        if (c.a() != 0 && c.b() != 0) {
            check(MathBasics.gcd(c.a(), c.b()) * c.expectLcm()
                  == Math.abs((long) c.a() * c.b()), "不变式: " + c);
        }
    }
    /* 交叉验证：两种筛法的质数集合必须一致 */
    List<Integer> linear = MathBasics.sieveLinear(10_000);
    boolean[] mark = MathBasics.sieveEratosthenes(10_000);
    for (int i = 2; i <= 10_000; i++) {
        check(mark[i] != linear.contains(i), "两筛不一致: " + i);
    }
}

四个动作：参数化（record 表驱动）、断言不变式（覆盖全部输入而不仅是想到的用例）、禁止硬编码长度、交叉验证（两套独立实现互校，最易暴露下标错）。

6. 复杂度与内存对照

算法	时间	空间	典型量级参考
`gcd`（迭代）	`O(log min(a,b))` 次取模	`O(1)`	32 位输入通常在几十次迭代内结束
单点试除	`O(sqrt(n))`	`O(1)`	单个 10^9 量级整数足够
埃氏筛	`O(n log log n)`	`O(n)` 字节	`n = 10^7` 起要考虑堆内存
线性筛	`O(n)`	`O(n)` + 质数表	用空间换最小质因子
杨辉三角（滚动）	`O(rows^2)`	`O(rows)`	行数受 `long` 溢出限制

不要用单次运行时间比较算法优劣——JIT 预热、GC、数组局部性会让常数因子差出数倍，真实差异按 JMH 口径测。

7. 排错

现象	原因	处理
`lcm` 结果变负数	`a * b` 中间量溢出	改 `a / g * b` 或提升到 `long`
`gcd(-7, 21)` 返回 `-7`	`%` 对负数保号	入口 `Math.abs`
`Math.abs(MIN_VALUE)` 仍为负	补码绝对值越界	拒绝该输入或提升到 `long`
筛法把 1 当质数	未显式标记下标 1	显式置 `0`、`1` 为已标记
`n = 0` 时越界	访问 `isComposite[1]`	加 `if (n >= 1)`
杨辉三角每行变 2 的幂	滚动数组从左往右	改为从右往左
组合数第 60 多行变负	`long` 溢出	取模或 `BigInteger`

8. 边界：什么时候该换工具

场景	换什么	理由
判定单个 10^18 量级整数	`BigInteger.isProbablePrime`	试除法量级不够
区间 `[L, R]` 且 `R` 极大	分块筛	分配 `R` 大小数组不现实
大量组合数查询	预处理阶乘 + 逆元	单次 `O(k)` 累计很贵
需要可复现的随机测试	固定种子 + 交叉验证	用例要能重放
需要微基准对比	JMH	`System.nanoTime` 测不出真实差异

最后一行的反面同样成立：埃氏筛与线性筛在 n = 10^6 下都在毫秒级，用秒表比较没有意义，噪声占主导。

9. 自测

a / gcd * b 与 a * b / gcd 的中间量上界分别是什么？
i <= Math.sqrt(n) 换成 (long) i * i <= n，修掉的是哪类输入上的错？
埃氏筛从 i * i 开始标记省掉了什么？它改变复杂度量级吗？
线性筛里删掉 if (i % p == 0) break; 会出现什么问题？
杨辉三角滚动数组从左往右更新会得到什么结果？为什么？
gcd(a,b) * lcm(a,b) == a * b 这条不变式在什么输入下会失效？