辗转相除法（欧几里得算法）——用减法求最大公约数的智慧

在古代，数学家欧几里得想出了一个聪明的办法求两个数的最大公约数，不需要列举所有因数，只需要重复做一件事：用大数除以小数，取余数；然后让原来的小数变成被除数，余数变成除数，继续除，直到余数为0。这时除数就是最大公约数。这个方法叫辗转相除法，也叫欧几里得算法。它是数学史上最古老的算法之一，至今仍被广泛使用，效率极高。

一、辗转相除法的原理

我们先用一个生活例子理解：假设你有48块糖和18块巧克力，想分成几份，每份糖和巧克力数量相同，而且正好分完，最多能分几份？这其实就是在求48和18的最大公约数。

操作步骤（以48和18为例）：

48 ÷ 18 = 2 余 12（48 = 18 × 2 + 12）
18 ÷ 12 = 1 余 6（18 = 12 × 1 + 6）
12 ÷ 6 = 2 余 0 → 余数为0，最大公约数是6

所以最多能分6份，每份有8块糖和3块巧克力。

核心公式：gcd(a, b) = gcd(b, a % b)，其中a > b（如果a < b，第一次除法会自动交换，因为a % b = a）。

为什么这样连续做下去能得到最大公约数？因为两个数的最大公约数，同时也是它们差的最大公约数。而取余运算本质上就是重复减法。例如，48和18的最大公约数，等于18和12（48-2×18）的最大公约数，依次类推，直到余数为0，除数就是答案。

二、代码实现：循环与递归

C++实现有两种常见风格：递归版和循环版。递归版代码简洁，循环版避免了函数调用开销，适合大数。

#include <iostream>
using namespace std;

// 递归版：一直调用自己，直到 b 为 0
int gcd(int a, int b) {
    if (b == 0) return a;          // 如果除数为0，返回被除数
    return gcd(b, a % b);          // 否则递归：新被除数=原除数，新除数=余数
}

// 循环版：用 while 循环代替递归
int gcd_loop(int a, int b) {
    while (b != 0) {               // 只要除数不是0就继续
        int r = a % b;             // 计算余数
        a = b;                     // 更新被除数
        b = r;                     // 更新除数
    }
    return a;                      // 循环结束，a 就是最大公约数
}

int main() {
    int x, y;
    cout << "请输入两个整数: ";
    cin >> x >> y;
    cout << "最大公约数(递归): " << gcd(x, y) << endl;
    cout << "最大公约数(循环): " << gcd_loop(x, y) << endl;
    return 0;
}

输入48 18，输出6。辗转相除法非常快，即使是很大的数也能瞬间算出来。

三、生活中的更多例子

例子1：分考卷
老师有240张数学卷子和90张语文卷子，要平均分给几个班级，每个班级得到的两种卷子数量相同，且不浪费。最多能分给几个班级？

240 ÷ 90 = 2 余 60
90 ÷ 60 = 1 余 30
60 ÷ 30 = 2 余 0 → 最大公约数是30，最多分给30个班。

例子2：切蛋糕
一个长方形蛋糕长36厘米，宽24厘米，要切成若干个正方形小块（边长相等，且没有剩余），正方形边长最大是多少？

36 ÷ 24 = 1 余 12
24 ÷ 12 = 2 余 0 → 边长最大12厘米。这样能切出最少的块数，既整齐又漂亮。

例子3：零花钱平分
小明攒了108元，小红攒了72元，他们想合起来买相同的文具套装，每套价格相同，正好把钱花完。每套最多多少钱？

108 ÷ 72 = 1 余 36
72 ÷ 36 = 2 余 0 → 每套最多36元。小明买3套，小红买2套。

四、新手容易犯的错误

忘记处理b为0的情况：递归版必须有if (b == 0) return a;，否则会无限递归导致栈溢出。循环版条件是while (b != 0)，写反了也会出错。
交换a和b的顺序：如果输入a < b，比如 gcd(18, 48)，第一次计算 18 % 48 = 18，然后 gcd(48, 18) 实际上是交换了位置，结果正确。但初学者可能误以为必须确保a ≥ b，其实算法本身会自动处理，不需要额外判断。
对负数处理：C++中取余运算的结果符号与被除数相同（比如 -7 % 3 = -1），所以如果输入负数，辗转相除法仍然能得到绝对值意义上的最大公约数，但结果可能为负。通常我们只在自然数范围内使用，所以最好先取绝对值。
混淆循环与递归：递归版每次调用都会创建新的函数栈，如果数字特别大（比如几百万位），可能栈溢出。实际竞赛中更推荐循环版，因为它只使用常数空间。

五、完整可运行代码（带输入检查）

下面是一个更完善的演示程序，包含了负数取绝对值和输入检查：

#include <iostream>
#include <cstdlib>  // 用于 abs 函数
using namespace std;

// 递归版：只处理非负整数
int gcd_recursive(int a, int b) {
    if (b == 0) return a;
    return gcd_recursive(b, a % b);
}

// 循环版
int gcd_iterative(int a, int b) {
    while (b != 0) {
        int r = a % b;   // 计算余数
        a = b;           // 更新被除数
        b = r;           // 更新除数
    }
    return a;
}

int main() {
    int x, y;
    cout << "请输入两个整数（空格隔开）: ";
    cin >> x >> y;

    // 避免负数：取绝对值
    x = abs(x);
    y = abs(y);

    // 如果其中一个为0，最大公约数是另一个数
    if (x == 0 && y == 0) {
        cout << "两个数都是0，没有定义最大公约数。" << endl;
        return 0;
    }
    if (x == 0) {
        cout << "最大公约数: " << y << endl;
        return 0;
    }
    if (y == 0) {
        cout << "最大公约数: " << x << endl;
        return 0;
    }

    // 正常计算
    int result1 = gcd_recursive(x, y);
    int result2 = gcd_iterative(x, y);
    cout << "递归版结果: " << result1 << endl;
    cout << "循环版结果: " << result2 << endl;
    return 0;
}

运行示例：

请输入两个整数（空格隔开）: 48 18
递归版结果: 6
循环版结果: 6

六、相关知识点指引

更相减损术：中国古代《九章算术》中也有类似方法，用反复相减代替取余，速度较慢但原理相通。

int gcd_by_sub(int a, int b) {
    while (a != b) {
        if (a > b) a -= b;
        else b -= a;
    }
    return a;
}

最小公倍数（LCM）：利用公式 lcm(a, b) = a * b / gcd(a, b)。注意先除后乘防止溢出。
扩展欧几里得算法：不仅能求最大公约数，还能找到一组整数解使得 ax + by = gcd(a, b)，常用于解不定方程和模逆元计算。
C++标准库函数：C++17 提供了 std::gcd（<numeric> 头文件），可以直接使用：
```
#include <numeric>
int result = gcd(48, 18);  // 返回6
```

辗转相除法是数论的基础算法，掌握它不仅能快速解决竞赛中的求最大公约数问题，还能为学习更高级的算法（如 RSA 加密、裴蜀定理）打下基础。