中级 · 算法

最大公约数

读两个正整数,输出它们的最大公约数。朴素做法（试每个因数）能过;欧几里得的做法（两千三百年前）是大多数人写的第一个真正聪明的算法。

一句话答案欧几里得算法 —— 只要 b 不为 0，就把 (a, b) 换成 (b, a % b)；最后 a 就是答案，即使 a、b 到 10⁹ 也只要 O(log min(a, b)) 步。

题目

输入: 一行,两个正整数 a 和 b(1 ≤ a, b ≤ 10⁹)。

输出: 它们的最大公约数。

样例:

输入输出
12 186
7 131

你的解答

main.cpp — 你的解答
「运行我的输入」用的自定义输入

判题在浏览器本地运行。死循环会在 3 秒后被自动中断 —— 但还是确保每个循环都有出口。代码随打随存。

卡住了？提示

提示 1 — 关键恒等式

任何同时整除 a 和 b 的数,也整除 a % b — 所以 gcd(a, b) = gcd(b, a % b)。每一步数字都在变小,而 a % b 恒小于 b,所以收敛极快。

提示 2 — 循环的形状

while (b != 0) { int t = a % b; a = b; b = t; } — 需要临时变量 t,因为先覆盖 a 会毁掉本来要放进 b 的值。(这正是交换两数（英文）的三行舞步。)b 到 0 时,a 就是答案。

题解（先自己试试！） 
#include <iostream>
using namespace std;

int main() {
    int a, b;
    cin >> a >> b;
    while (b != 0) {
        int t = a % b;
        a = b;
        b = t;
    }
    cout << a << endl;
    return 0;
}

为什么它碾压朴素做法:输入到十亿,试除法最多十亿次循环;欧几里得最多约 45 次(最坏情况是相邻的斐波那契数 — 见下一题)。手推 gcd(12, 18):(12,18) → (18,12) → (12,6) → (6,0) → 答案 6。想通之后,LCM 只差一行:a * b / gcd。

深度解析

为什么这样做对

欧几里得恒等式 gcd(a,b) = gcd(b, a % b) 是至今仍在日常使用的最古老非平凡算法，也是「每一步都让问题变小」的原型。

代价

O(log min(a,b))。相邻两个斐波那契数是最坏情况。

常见错法

  • while (b > 0) 遇到负数会出问题，先取绝对值。
  • 从 min(a,b) 往下逐个试是 O(n)，碰到大且互质的输入直接超时。

下一步

同样「每步变小」的递归：斐波那契。

记住这两句

  • gcd(a,b) = gcd(b, a % b)。
  • 是 O(log n) 不是 O(n)——朴素循环慢一千倍。
🐞 这段是错的 —— 点开,亲手让它挂一次

打印 b，可循环结束时它已经是 0

#include <iostream>
using namespace std;

int main() {
    int a, b;
    cin >> a >> b;
    while (b > 0) {
        int t = a % b;
        a = b;
        b = t;
    }
    cout << b << endl;
    return 0;
}