辗转相除法——找两个数的最大公约数

辗转相除法：像量绳子一样求最大公约数

你有没有遇到过这样的问题：要把两块不同大小的蛋糕切成若干等份，每份大小一样，而且每块蛋糕都不能有剩余，最多能切成多大的块？或者，你和朋友分零食，你手里有48颗糖，他有18颗糖，你们想把这些糖分成相同数量的堆，每堆糖数尽量多，但每堆的糖数必须是整数，而且不能有剩糖，最大能每堆放几颗？

这种问题的答案就是两个数的最大公约数（也叫最大公因数）。今天我们要学一个超级快速的方法——辗转相除法（也叫欧几里得算法），它就像用尺子量布料一样，几下就能找到答案。

什么是最大公约数？

继续用蛋糕来理解：把两个数像蛋糕一样切成大小相同的块，能切出的最大块就是最大公约数。比如12和18，都能被6整除，6就是它们的最大公约数。你还可以试试：8和12的最大公约数是4，因为8÷4=2，12÷4=3，而且没有比4更大的数能同时整除它们俩了。

生活中的例子：
你和同学各有一堆铅笔，你20支，他28支。你想把两人的铅笔重新分成每组相同数量的笔，每组尽量多，并且不剩笔。那么每组最多能放多少支？其实就是求20和28的最大公约数。20和28的公约数有1、2、4，最大的是4，所以每组4支。

辗转相除法怎么工作？

想象你有两根长度不同的绳子，想找一根能同时量完两根绳子的最长小绳。你拿长绳子去量短绳子，剩下的余数再用短绳子去量，一直重复，直到余数为0。最后那根绳子就是答案。

用数学语言来说：
两个正整数a和b（假设a >= b），用a除以b得到余数r。

如果r = 0，那么b就是最大公约数。
如果r ≠ 0，那么用b和r继续做同样的除法（也就是把原来的除数变成新的被除数，余数变成新的除数），重复直到余数为0。

我们来手动算一个例子：
求48和18的最大公约数。

步骤1：48 ÷ 18 = 2……余12（因为 18×2 = 36，48 - 36 = 12）
步骤2：18 ÷ 12 = 1……余6（12×1 = 12，18 - 12 = 6）
步骤3：12 ÷ 6 = 2……余0（6×2 = 12，正好除尽）
余数为0，所以最后的除数6就是最大公约数。

你可能会想：为什么最后那个除数就是答案？其实每次除法都相当于在“缩小问题规模”，但保证公约数不变。比如48和18的公约数，和18与12的公约数是一样的，再和12与6的公约数也一样……最后6和0的公约数就是6。所以6就是48和18的最大公约数。

用生活例子再理解一遍（分步讲解）

假设你有一条48厘米的绳子和一条18厘米的绳子，想找一根最长的小绳，能正好量完这两根绳子（没有剩余）。

用48厘米的绳子去量18厘米的绳子：48里最多有几个18？2个，48 - 2×18 = 12，剩下12厘米。
现在用18厘米的绳子去量剩下的12厘米：18里最多有1个12，18 - 1×12 = 6，剩下6厘米。
再用12厘米的绳子去量剩下的6厘米：12里正好有2个6，剩下0厘米。
最后剩下的那根6厘米的绳子，就是我们要找的最长小绳！

你看，整个过程就是用大数减小数的倍数，得到余数，然后交换位置继续。这个算法对两个数的大小顺序没有要求——如果一开始a比b小，a % b的结果就是a本身，然后自动交换了。

C++代码实现

写法一：递归（自己调用自己）

保留你现有的代码，它已经非常清晰了：

#include <iostream>
using namespace std;

// 辗转相除法（递归写法）
int gcd(int a, int b) {
    if (b == 0) return a;          // 如果余数为0，返回当前的被除数
    return gcd(b, a % b);          // 否则用余数继续
}

int main() {
    int num1, num2;                // 定义两个整数
    cout << "请输入两个正整数：";
    cin >> num1 >> num2;
    cout << "最大公约数是：" << gcd(num1, num2) << endl;
    return 0;
}

运行示例：输入48 18，输出6。

写法二：循环（不用递归，更省内存）

如果你不想用递归（递归可能会让新手觉得绕），可以用while循环实现：

#include <iostream>
using namespace std;

int gcd(int a, int b) {
    int remainder;                 // 存储余数
    while (b != 0) {               // 只要除数不是0就继续
        remainder = a % b;         // 计算a除以b的余数
        a = b;                     // 把原来的除数变成新的被除数
        b = remainder;             // 把余数变成新的除数
    }
    return a;                      // 最后a就是最大公约数
}

int main() {
    int num1, num2;                // 两个输入数
    cout << "请输入两个正整数：";
    cin >> num1 >> num2;
    cout << "最大公约数是：" << gcd(num1, num2) << endl;
    return 0;
}

两种写法效果完全一样。你可以选择你更习惯的那种。

新手容易犯的错误

忘记考虑0的情况
如果输入中有一个是0，比如求0和15的最大公约数，按照定义，任何数和0的最大公约数是那个非0的数本身。但我们的程序里如果a=0, b=15，第一次循环a%b=0%15=0，然后a=15, b=0，下一次循环b==0就跳出，返回a=15，结果是正确的。但如果两个都是0，数学上没定义，程序会返回0（因为第一次循环a%b=0%0会出错！）。所以编程时一般要求输入正整数。
误以为要先判断谁大谁小
很多同学会写：
```
if (a < b) swap(a, b);  // 交换，保证a >= b
```
其实不需要！因为如果a < b，那么a % b的结果就是a本身，例如3 % 5 = 3。下一次递归时变成gcd(5, 3)，自动把大的放前面了。循环写法同理，第一次a % b = a，然后a = b, b = a（原来的a），实际上也交换了。所以不需要额外判断。
忘记包含头文件
使用cin/cout一定要写#include <iostream>，使用using namespace std;。
递归层数过多
对于非常大的两个数（比如几十亿），递归可能因为调用次数太多而栈溢出。但一般我们学习的范围内没问题。如果担心，推荐用循环写法。

完整可运行示例

下面是一个完整程序，它允许用户反复输入多组数，输入0 0时退出：

#include <iostream>
using namespace std;

// 循环实现最大公约数
int gcd(int a, int b) {
    int remainder;                 // 余数
    while (b != 0) {
        remainder = a % b;
        a = b;
        b = remainder;
    }
    return a;
}

int main() {
    int x, y;                      // 两个输入数
    cout << "求两个正整数的最大公约数（输入0 0结束）" << endl;
    while (true) {
        cout << "请输入两个数：";
        cin >> x >> y;
        if (x == 0 && y == 0) break;  // 输入两个0则退出
        if (x <= 0 || y <= 0) {       // 简单检查正数
            cout << "请输入正整数！" << endl;
            continue;
        }
        int result = gcd(x, y);
        cout << "最大公约数是：" << result << endl;
    }
    return 0;
}

运行示例：

求两个正整数的最大公约数（输入0 0结束）
请输入两个数：48 18
最大公约数是：6
请输入两个数：100 75
最大公约数是：25
请输入两个数：0 0

为什么它很快？

你可能会想：“为什么不直接从1开始一个个试，看能不能同时整除两个数？”比如求48和18的最大公约数，从1试到18（小数），要试18次，而且每次都要做除法。但如果用辗转相除法，我们只做了3次除法就得到了答案。因为每次除法都会让数字快速变小——余数最大不超过较小数的一半（有时甚至更小），所以大约log(min(a,b))次就能完成，对于百万级的数字，也只需要十几步。

所以当数字很大时，辗转相除法是绝对的首选方法。