CC++ & Algorithm

辗转相除法（欧几里得算法）

较难5
语言版本：通用
概述：欧几里得算法是求最大公约数最经典的方法，通过反复取余将问题规模缩小，用故事讲解其原理和证明，并给出两种语言的实现。

轻松理解“辗转相除法”：求最大公约数的欧几里得算法

导语：什么是最大公约数？为什么要学它？

当你和好朋友分零食时，怎样公平地分，让每个人拿到相同数量的糖果？比如你有 48 颗糖，朋友有 18 颗糖，你们想分成几堆，每堆糖果数相同且都是整数，而且堆数尽可能少（每堆尽可能大）。那么每堆最多能放多少颗？答案就是 48 和 18 的最大公约数，也就是 6 颗。每堆 6 颗，你能分 8 堆，朋友分 3 堆。

最大公约数（Greatest Common Divisor, GCD） 就是能同时整除两个数的最大的那个数。欧几里得算法（也叫辗转相除法）是求 GCD 最经典、最高效的方法，它用“反复取余”的方式飞快地算出答案，即使数字大到几百位也只需眨眼功夫。今天我们就从生活例子出发，一步步搞懂它。

生活中的例子

工匠量木板的故事

古代有一位聪明的工匠，他有一把尺子和一根绳子，想量出两张木板的最大公共长度。木板 A 长 18 尺，木板 B 长 12 尺。他想找一把最长的尺子，能同时量完两张木板而不剩。他先把 A 对折，比 B 长 6 尺，于是把 A 换成 6 尺，用 B（12 尺）和 6 尺比，B 是 6 尺的两倍，于是 6 尺就是答案。其实这个过程就是辗转相除法。

分蛋糕的故事

再想想“分蛋糕”的故事：小明和小红分别有一块长方形蛋糕，长度分别是 a 和 b，他们想把蛋糕切成尽可能大的正方形小块，且不能有浪费。切出的正方形边长就是 a 和 b 的最大公约数。小明的蛋糕长 30 厘米，小红的蛋糕长 42 厘米，最大正方形边长是多少？用辗转相除法：42 和 30，42 除以 30 余 12，30 除以 12 余 6，12 除以 6 余 0，所以边长是 6 厘米。

更多贴近生活的例子

  • 分组问题：学校运动会有 56 个男生和 42 个女生，想分成若干队伍，每队男生人数相同、女生人数也相同，每队人数尽可能多。每队多少人？就是求 gcd(56,42) = 14，每队 14 人（其中男生 4 个，女生 3 个）。
  • 零花钱问题：你每周有 20 元零花钱，朋友每周有 35 元，你们想攒一样多的钱买礼物，在不找零的情况下，最少需要几周？需要找到 20 和 35 的最大公约数 5，然后分别攒 4 周和 7 周就能有相同金额（20 的倍数和 35 的倍数相等）。其实更直接的是求两个数的最小公倍数，但最大公约数是求最小公倍数的关键。

数学原理与公式推导

欧几里得算法（Euclidean Algorithm）原理

设 a、b 是两个正整数，且 a ≥ b。用 b 去除 a，得到商 q 和余数 r，满足： a = q * b + r，其中 0 ≤ r < b。 则 gcd(a,b) = gcd(b,r)。

为什么相等？ 因为如果 d 能整除 a 和 b，那么 d 也能整除 r = a - qb；反过来，如果 d 能整除 b 和 r，那么 d 也能整除 a = qb + r。所以 a 和 b 的公约数集合与 b 和 r 的公约数集合完全相同，因此最大公约数相等。

重复这个过程：用 b 和 r 继续做除法，得到新的余数，直到余数为 0。此时，当前的非零除数就是最大公约数。

数学公式表示

设 r₀ = a, r₁ = b，反复进行： r₀ = q₁ * r₁ + r₂ r₁ = q₂ * r₂ + r₃ ... r_{n-2} = q_{n-1} * r_{n-1} + r_n r_{n-1} = q_n * r_n + 0 则 gcd(a,b) = r_n。

手算步骤演示（从简单到复杂）

例子 1：求 gcd(48, 18)

  • 48 ÷ 18 = 2 余 12（因为 2×18=36，48-36=12）
  • 18 ÷ 12 = 1 余 6（1×12=12，18-12=6）
  • 12 ÷ 6 = 2 余 0（2×6=12，正好整除）
  • 余数为 0，最后的除数 6 就是最大公约数。所以 gcd(48,18)=6。

例子 2：求 gcd(30, 42)（蛋糕问题）

  • 42 ÷ 30 = 1 余 12
  • 30 ÷ 12 = 2 余 6
  • 12 ÷ 6 = 2 余 0 → gcd=6

例子 3：求 gcd(100, 15)

  • 100 ÷ 15 = 6 余 10（6×15=90，100-90=10）
  • 15 ÷ 10 = 1 余 5
  • 10 ÷ 5 = 2 余 0 → gcd=5

例子 4：求 gcd(17, 5)（互质的数）

  • 17 ÷ 5 = 3 余 2
  • 5 ÷ 2 = 2 余 1
  • 2 ÷ 1 = 2 余 0 → gcd=1 说明 17 和 5 互质（最大公约数为 1）。

时间复杂度

欧几里得算法的时间复杂度大约为 O(log min(a,b))，非常快。即使对很大的数（比如几百位），也只需要几十次除法就能算出结果。因为每次取余后，余数至少减少一半（严格来说，每次迭代后两数乘积至少减半），所以运算次数不超过 log₂(min(a,b))。

编程实现思路

在写代码之前，我们先明确步骤：

  1. 输入两个正整数 a, b。
  2. 重复：用 a 除以 b 得到余数 r，然后令 a = b, b = r。
  3. 当 b 变成 0 时，a 就是最大公约数。

可以用迭代（循环）或递归（函数调用自身）两种方式实现。

注意：不需要提前交换大小

很多同学会想：如果 a < b 怎么办？比如求 gcd(10,20)。第一次用 a%b 时，10%20=10（因为 10<20，商为 0，余数为 10），然后 a 变成 20，b 变成 10，相当于自动交换了。所以算法对任何正整数都有效。

C++ 完整代码实现

我们给出迭代和递归两种版本，每行变量都加了中文注释，方便理解。

#include <iostream>
using namespace std;

// 迭代版本：用 while 循环反复取余
int gcd_iterative(int a, int b) {
    while (b != 0) {
        int r = a % b;  // 计算 a 除以 b 的余数
        a = b;          // 更新 a 为原来的除数 b
        b = r;          // 更新 b 为余数 r
    }
    return a;           // 结束循环时 b=0，a 就是最大公约数
}

// 递归版本：函数调用自身
int gcd_recursive(int a, int b) {
    if (b == 0) return a;               // 终止条件：当 b=0 时，a 就是结果
    return gcd_recursive(b, a % b);     // 否则递归求 gcd(b, a%b)
}

int main() {
    int x, y;
    cout << "请输入两个正整数：";
    cin >> x >> y;

    // 调用迭代函数
    int result = gcd_iterative(x, y);
    cout << "迭代法求得最大公约数：" << result << endl;

    // 调用递归函数
    cout << "递归法求得最大公约数：" << gcd_recursive(x, y) << endl;

    return 0;
}

运行示例：

请输入两个正整数：48 18
迭代法求得最大公约数：6
递归法求得最大公约数：6

Python 完整代码实现

Python 的写法更简洁，尤其是同时赋值的小技巧。同样给出两种版本，并附上注释。

# 迭代版本
def gcd_iterative(a, b):
    while b != 0:
        # 同时赋值：新 a = 旧 b，新 b = 旧 a % 旧 b
        a, b = b, a % b
    return a

# 递归版本
def gcd_recursive(a, b):
    if b == 0:
        return a
    return gcd_recursive(b, a % b)

# 主程序
if __name__ == "__main__":
    x = int(input("请输入第一个正整数："))
    y = int(input("请输入第二个正整数："))

    print("迭代法求得最大公约数：", gcd_iterative(x, y))
    print("递归法求得最大公约数：", gcd_recursive(x, y))

    # 验证：Python 内置 math.gcd 函数
    import math
    print("内置函数求得最大公约数：", math.gcd(x, y))

运行示例：

请输入第一个正整数：48
请输入第二个正整数：18
迭代法求得最大公约数： 6
递归法求得最大公约数： 6
内置函数求得最大公约数： 6

常见错误（新手容易犯的坑）

错误 1：输入负数或零

欧几里得算法通常针对正整数。如果输入负数，取余结果可能负，导致循环不结束或结果错误。解决方法：在函数开头加一个取绝对值的操作，比如 a = abs(a); b = abs(b)。但中小学生通常只处理正整数，所以只要确保输入时提示“请输入正整数”即可。

错误 2：忘记处理 b=0 的情况（递归版本）

递归函数必须有一个终止条件 if b == 0: return a，否则会无限递归导致栈溢出。迭代版本中 while b != 0 也保证了循环结束。

错误 3：以为必须保证 a >= b

有些同学会先写 if (a < b) swap(a,b);，但这个步骤是不必要的。算法自动处理了大小关系，加了也不影响结果，但会让你多写代码。

错误 4：混淆求余和整除

注意是用 % 求余数，不是用 /。例如 a % b 得到余数，如果写成 a / b 会得到浮点数（Python3中）或整数除法（C++中），完全不对。

错误 5：递归深度太大

虽然欧几里得算法递归深度通常很小（log级别），但如果输入的两个数非常大且互为斐波那契数（比如 1000000 和 999999），递归深度可能上百层。一般编程语言默认递归限制足够（如 Python 默认 1000 层），但为了保险，迭代版本更推荐。

完整示例：用欧几里得算法解决实际问题

约分分数

把分数 48/18 约成最简分数：分子分母同时除以它们的最大公约数 6，得到 8/3。代码实现：

def simplify_fraction(num, den):
    g = gcd_iterative(num, den)
    return num // g, den // g

print(simplify_fraction(48, 18))  # 输出 (8, 3)

判断两个数是否互质

如果 gcd(a,b) == 1，则 a 和 b 互质。比如 17 和 5 互质。

求最小公倍数（LCM）

最小公倍数 = a * b / gcd(a,b)。因为最大公约数已经求出，就可以轻松算出 LCM。

def lcm(a, b):
    return a * b // gcd_iterative(a, b)

print(lcm(48, 18))  # 输出 144（因为 48*18/6=144）

相关知识点指引

学会了欧几里得算法，你还能继续探索：

  • 扩展欧几里得算法：不仅能求最大公约数，还能找到整数 x, y 使得 ax + by = gcd(a,b)。这是解不定方程、求模逆元的基础。
  • 最小公倍数（LCM）：和 GCD 紧密相关，如上所述。
  • 分数运算：约分、通分都依赖 GCD。
  • 密码学：RSA 加密算法中需要计算大素数的 GCD。
  • 游戏设计：比如英雄联盟里技能冷却时间的最简比例、资源分配等。

希望你用辗转相除法，轻松解决所有“分东西”的烦恼！

例题精讲

1单选题

欧几里得算法求最大公约数依据的数学定理是？

Agcd(a,b) = gcd(b, a mod b)
Bgcd(a,b) = gcd(a-b, b)
Cgcd(a,b) = gcd(a+b, b)
Dgcd(a,b) = gcd(b, a)
2判断题

欧几里得算法的时间复杂度为O(log min(a,b))，其中a和b是输入的正整数。

3填空题
以下是用递归实现欧几里得算法的C语言代码，请填写空白处的表达式。

int gcd(int a, int b) {
    if (b == 0) return a;
    return ___;
}
4单选题

使用欧几里得算法求gcd(123, 45)时，第一次取余操作的结果是多少？

A33
B12
C3
D18
5判断题

在欧几里得算法中，a和b的最大公约数等于a与a mod b的最大公约数。