【例35.3】 最大公约数

解题思路

欧几里得算法：不断把 (a,b) 换成 (b,a%b)，直到 b=0，输出 a。

正确性说明

a与b的公约数集合等于b与a%b的公约数集合，每次替换不改变最大公约数；终止时gcd(a,0)=a。

易错点

C++11没有std::gcd，使用手写循环。

复杂度

时间O(log min(a,b))，空间O(1)。

参考代码（C++11）

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    long long a, b;
    cin >> a >> b;
    while (b) {
        long long r = a % b;
        a = b;
        b = r;
    }
    cout << a << "\n";
    return 0;
}