如何求最大公约数和最小公倍数？（欧几里得算法）

简化版

最大公约数（GCD）用欧几里得算法（辗转相除法）：gcd(a, b) = gcd(b, a % b)，不断用较大数对较小数取余，直到余数为 0，此时的除数就是 GCD。**最小公倍数（LCM）**由 GCD 推出：lcm(a, b) = a / gcd(a, b) * b（先除后乘防溢出）。辗转相除法极快，时间约 O(log(min(a,b)))。

详细版

// 最大公约数：辗转相除（递归）
int gcd(int a, int b) {
    return b == 0 ? a : gcd(b, a % b);
}

// 迭代版
int gcdIterative(int a, int b) {
    while (b != 0) {
        int t = a % b;
        a = b;
        b = t;
    }
    return a;
}

// 最小公倍数：先除后乘，防溢出
int lcm(int a, int b) {
    return a / gcd(a, b) * b;
}

GCD 核心：gcd(a, b) = gcd(b, a % b)，余数为 0 时除数即答案。
LCM 公式：lcm = a * b / gcd(a, b)，写成 a / gcd * b 先除后乘避免 a*b 溢出。
复杂度：O(log(min(a,b)))，非常快。

完整版教学

一、欧几里得算法：为什么 gcd(a,b) = gcd(b, a%b)

最大公约数（Greatest Common Divisor）是能同时整除 a 和 b 的最大正整数。辗转相除法基于一个关键定理：

gcd(a, b) = gcd(b, a mod b)

为什么成立：设 d 是 a 和 b 的公约数（d 整除 a、也整除 b）。因为 a = k*b + (a mod b)，所以 a mod b = a - k*b。既然 d 整除 a 和 b，它也整除 a - k*b = a mod b。反过来同理，b 和 a mod b 的公约数也整除 a。所以 (a, b) 的公约数集合 = (b, a mod b) 的公约数集合，它们的最大公约数自然相等。

于是问题从 (a, b) 缩小到 (b, a mod b)——数越变越小，直到 b == 0，此时 gcd(a, 0) = a（a 和 0 的最大公约数是 a），递归结束。

二、手算走一遍

求 gcd(48, 36)：

gcd(48, 36) = gcd(36, 48 % 36) = gcd(36, 12)
gcd(36, 12) = gcd(12, 36 % 12) = gcd(12, 0)
b == 0，返回 12。

所以 gcd(48, 36) = 12。每一步余数快速减小，几步就到 0。

三、递归与迭代两种写法

递归版：return b == 0 ? a : gcd(b, a % b); 一行，最简洁，符合定义。
迭代版：用 while (b != 0) 不断 (a, b) = (b, a % b)，避免递归栈开销。

两者等价，面试写哪个都行。注意参数无需保证 a > b——若 a < b，第一次 a % b = a，gcd(b, a) 自动交换过来，所以不用特意排序。

四、最小公倍数 LCM：由 GCD 推出

最小公倍数（Least Common Multiple）是 a 和 b 的公共倍数中最小的。有一个漂亮的关系：

a * b = gcd(a, b) * lcm(a, b)

即 lcm(a, b) = a * b / gcd(a, b)。

直觉：a 和 b 的乘积「重复算了」它们公共的那部分（gcd），除掉一份 gcd 就得到最小公倍数。

防溢出写法：直接 a * b 可能溢出（两个较大的 int 相乘超 int 范围）。所以写成 a / gcd(a,b) * b——先除后乘：a / gcd 一定整除（gcd 是 a 的约数），先缩小 a 再乘 b，降低溢出风险。必要时用 long。

五、复杂度与应用

时间 O(log(min(a,b)))：每两步至少让较小数减半（斐波那契是最坏情况），所以对数级，极快。
应用：分数化简（分子分母同除 gcd）、通分（用 lcm）、判断互质（gcd == 1）、循环节问题、以及扩展欧几里得（求 ax + by = gcd 的解，用于求模逆元、解线性同余）。
扩展欧几里得：gcd 的进阶版，能同时求出系数 x、y，是数论题（模逆元、中国剩余定理）的基础，属加分点。

六、余数替换为什么保持公约数集合

写 a=qb+r。若 d 同时整除 a、b，则也整除 r=a-qb；反过来若 d 整除 b、r，也整除 a=qb+r。两边的公约数集合完全相同，因此最大公约数相同，这给出了欧几里得算法的严格证明。

求 gcd(252,105)
252 = 2×105 + 42 -> gcd(105,42)
105 = 2×42 + 21 -> gcd(42,21)
42 = 2×21 + 0 -> 停止
gcd = 21
lcm = 252/21×105 = 1260
先除后乘避免 252×105 的中间值更大

校验维度	本题必须保持的结论
循环/递推不变量	每轮替换 `(a,b)=(b,a%b)` 保持 gcd 不变，且第二个非负参数严格减小。
边界条件	`gcd(a,0)=
复杂度与代价	欧几里得算法 O(log min(a,b))，迭代空间 O(1)。
自检方式	用最小输入、典型输入和触及边界的输入分别手推，结果应与定义一致。

这组推演的作用不是替代证明，而是把抽象规则落到每一步状态变化上。面试写完代码后，应主动指出不变量如何保证不漏解，以及边界为何不会越界或死循环。若手推结果与定义不一致，应先修正状态语义，而不是继续给代码打补丁。

七、面试现场如何验证这道题

数学题不能只凭样例相信公式，必须同时核对定义域、推导条件和定宽整数边界。本题应先复述这条不变量：每轮替换 (a,b)=(b,a%b) 保持 gcd 不变，且第二个非负参数严格减小。只有代码的初始化、更新顺序和终止条件都维持它，样例通过才具有证明力。

典型路径从“求 gcd(252,105)”开始手推，最后应得到“先除后乘避免 252×105 的中间值更大”。
边界复核：gcd(a,0)=|a|；若允许负输入，应先取绝对值并注意最小整数绝对值溢出。
代价复核：欧几里得算法 O(log min(a,b))，迭代空间 O(1)。
用 0、1、最小合法值和最大合法值检查公式的定义域。
乘法、取绝对值或取负前先判断是否可能触及 Integer.MIN_VALUE 等不对称边界。
若算法依赖单调性、抵消或整除关系，要明确题设保证何时成立、何时必须额外验证。

最后要主动构造一个“少写一次循环、改变一个不等号或交换两行更新就会失败”的反例。能说清反例破坏了哪条不变量，比只报出复杂度更能证明真正掌握了算法。

记忆钩子：本题的代码可以压缩，但“每轮替换 (a,b)=(b,a%b) 保持 gcd 不变，且第二个非负参数严格减小。”这条正确性主线不能省。

八、常见误区与追问

误区：GCD 只能通过枚举因子求。 欧几里得算法利用余数不变性，复杂度是对数级。
误区：LCM 应先计算 a*b/gcd。 先乘可能溢出，安全写法是 (a/gcd)*b，并使用足够宽类型。
误区：gcd(a,0) 没有定义。 标准约定为 |a|，也正是欧几里得算法的终止条件。
追问：为什么余数序列一定结束？ 非零余数满足 0<=r<b，正整数严格下降不可能无限进行。
追问：多个数的 GCD 怎么求？ 利用结合性逐个归并：gcd(gcd(a,b),c)。
追问：裴蜀等式如何扩展？ 扩展欧几里得算法同时求 x、y，使 ax+by=gcd(a,b)。

九、加强记忆

最大公约数 GCD = 辗转相除（欧几里得）：gcd(a, b) = gcd(b, a % b)，不断用余数替代，b == 0 时除数 a 即答案。原理：(a,b) 和 (b, a mod b) 的公约数集合相同。最小公倍数 LCM = a / gcd(a,b) * b（由 a*b = gcd*lcm 推出，先除后乘防溢出）。时间 O(log(min(a,b)))，极快。应用：分数化简、判互质（gcd==1）、通分。进阶扩展欧几里得求系数解同余。核心两式：gcd(a,b)=gcd(b,a%b)、lcm=a/gcd*b。

简化版

详细版