辗转相除法：古老而优雅的数学之美

辗转相除法（欧几里得算法）不仅是求最大公约数（GCD）的工具，更是理解“递归”和“分治”思想的入门砖。

1. 核心逻辑：一句话记忆

“大数除以小数，取余代大数，直到余数为零。”

其数学表达式极为简洁：gcd(a, b) = gcd(b, a % b)。当 b 变为 0 时，剩下的 a 就是我们要找的那个最大的“公约数”。

2. 为什么我们要背下这个模板？

在 LeetCode 中，它往往不是题目的全部，而是某个复杂逻辑的一环。如果你能闭着眼写出 GCD，你就能快速解决：

• 🎯 [LeetCode 149. 直线上最多的点数]：需要用 GCD 来化简斜率。
• 🎯 [LeetCode 365. 水壶问题]：著名的裴蜀定理应用，本质就是看目标水量是否是 GCD 的倍数。
• 🎯 [最小公倍数 LCM]：有一个核心公式必背：LCM(a, b) = (a * b) / GCD(a, b)。

3. 标准代码模板（递归 vs 迭代）

我个人更推荐递归版，因为它完美契合数学定义，且代码极其短小：

/**
 * 求最大公约数 (Greatest Common Divisor)
 */
function gcd(a, b) {
    // 递归基准条件：当余数为 0 时，b 为 0，此时 a 就是最大公约数
    return b === 0 ? a : gcd(b, a % b);
}

// 迭代版（如果你担心递归栈溢出，虽然 GCD 极少发生）
function gcdIterative(a, b) {
    while (b !== 0) {
        let temp = a % b;
        a = b;
        b = temp;
    }
    return a;
}

4. 应用场景与“心法”

• 化简分数：分子分母同时除以 gcd(numerator, denominator)。
• 平铺问题：用正方形地砖铺满长方形地面，正方形的最大边长就是长宽的 GCD。
• 周期同步：两个不同周期的闹钟同时响起，下一次同时响起的间隔就是它们的 LCM（由 GCD 求得）。

锻造感悟： 辗转相除法展示了算法中最迷人的一面——收敛性。无论输入的数字多大，取余操作都会让规模以惊人的速度缩小。这提醒我，面对复杂问题，通过不断的“取余（去除冗余，聚焦核心）”，终能看到问题的本原。