P4364 找出最大公约数（基础）

解题思路

最大公约数就是两个数公有的约数里最大的那个。比如 24 和 8，8 既是 24 的约数也是 8 的约数，所以最大公约数是 8；再看 35 和 28，它们的约数分别是 1、5、7、35 和 1、2、4、7、14、28，公有的约数是 1 和 7，最大的是 7。

最笨的办法是从小的那个数开始，一个数一个数往下试，看能不能同时整除两个数。但如果数字很大（比如几十亿），一个个试就太慢了。

这里有一个又快又巧妙的办法，叫"辗转相除法"（也叫欧几里得算法）：用 a 除以 b 取余数 t，然后把 b 当成新的 a、把 t 当成新的 b，重复这个过程，直到余数为 0，这时候的 a 就是最大公约数。

为什么可以这样？因为"a 和 b 的公约数"和"b 和 a%b 的公约数"完全一样，我们只是把问题变小了，公约数却一个都没丢，所以一直缩到最后剩下的就是最大公约数。

举个例子：求 35 和 28。35 % 28 = 7，变成求 28 和 7；28 % 7 = 0，余数为 0，最大公约数是 7。

边界情况：如果一个数正好是另一个数的倍数（比如 24 和 8），第一次取余就是 0，循环一次就出结果；如果两个数相等（比如 6 和 6），6 % 6 = 0，答案就是 6。即使输入时小的数在前（比如 8 和 24），8 % 24 = 8，下一轮自动变成 a=24、b=8，照样正确。

参考代码

// 程序用途：输入两个整数，用辗转相除法求它们的最大公约数
#include <iostream>
using namespace std;

int main() {
    int a, b;
    cin >> a >> b;
    // 辗转相除：用a除以b取余数，余数不为0就继续
    while (b != 0) {
        int t = a % b;        // t = a除以b的余数
        a = b;                // 把除数b当成新的被除数a
        b = t;                // 把余数t当成新的除数b
    }
    cout << a << endl;        // 余数为0时，a就是最大公约数
    return 0;
}

复杂度分析

每做一次取余，两个数都会明显变小，循环次数大约是 O(log min(a,b)) 的数量级；空间只用了几个变量，额外空间复杂度是 O(1)。