辗转相除法：用“分蛋糕”的思想求最大公约数

你有没有试过和好朋友平分一包零食？如果零食有48块，你俩要分成一样多的份数，一次可以分几块？假如你俩还各有一份零食，一份48块，一份18块，你想把这些零食重新包装成每袋数量相同的大礼包，每袋最多能装几块，才能刚好分完？这个“每袋最多能装几块”就是两个数的最大公约数。

辗转相除法（也叫欧几里得算法）就是用来快速求最大公约数的一种古老又聪明的方法。它像切蛋糕一样，用大块去切小块，总能把两个数“切”出它们共同的最大份量。

什么是最大公约数？先看一个生活例子

假设你买了24块巧克力，朋友买了16块巧克力，你们想把这些巧克力混在一起，分成几堆，每堆数量相同，而且每堆都要是整数块。每堆最多能分几块？答案是8块，因为24和16的公约数有1、2、4、8，其中最大的是8。8就是24和16的最大公约数（gcd）。记作：gcd(24, 16) = 8。

最大公约数帮助我们在分东西、约分分数、计算周期等问题中找到“共同的最大单位”。

辗转相除法的核心思想：用余数代替减法

其实求最大公约数有一种笨办法：把两个数不断相减，直到两个数相等。比如24和16：

• 24 - 16 = 8 → 现在有16和8
• 16 - 8 = 8 → 现在有8和8
• 8 = 8，所以最大公约数是8。

但这样太慢了，如果数很大，要减很多次。辗转相除法用取余（求余数）代替多次减法，一步到位：

两个整数 a 和 b（假设 a ≥ b），它们的最大公约数等于 b 和 (a 除以 b 的余数) 的最大公约数。

不断重复这个规则，直到余数为0，此时另一个数就是最大公约数。

为什么？因为如果 d 能整除 a 和 b，那么 d 也一定能整除 a 除以 b 的余数 r = a - b × 商。所以 gcd(a,b) = gcd(b, r)。而 r 比 b 小，每次计算都让数字变小，最终一定能得到结果。

一步步来：用48和18“切蛋糕”

想象你有一个48克的大蛋糕，和一个18克的小蛋糕。你想把它们切成若干块同样大小的蛋糕块，每块要尽可能大。辗转相除法的过程就像用大蛋糕去切小蛋糕：

1. 48 切 18：48 ÷ 18 = 2 余 12
   意思是：大蛋糕可以分出2个18克的小蛋糕，还剩下12克。此时我们关心的是“剩下的12克和小蛋糕18克”的最大公约数（因为剩下的12克和原来的18克都是原来大蛋糕的“倍数”关系）。

2. 18 切 12：18 ÷ 12 = 1 余 6
   现在用剩下的12克蛋糕去“切”18克蛋糕？其实是换过来：用较小的数12去除以余数？注意规则是：用前一步的除数（18）除以余数（12），得到新的余数6。这相当于用12克蛋糕去切18克，剩下6克。

3. 12 切 6：12 ÷ 6 = 2 余 0
   最后用6去切12，正好切完，余数为0。此时除数6就是最大公约数。

所以最大公约数是6。验证一下：48 ÷ 6 = 8，18 ÷ 6 = 3，都能整除，而且6是最大的。

用Python代码实现：循环版本

代码超级简单，核心只有一行交换赋值：

def gcd(a, b):
    # 辗转相除法求最大公约数，循环直到余数为0
    while b != 0:               # 当除数不为0时继续
        a, b = b, a % b         # 新的a变成原来的b，新的b变成a除以b的余数
    return a                    # 最后b=0，a就是最大公约数

为什么这样写？

• 初始时 a、b 任意大小，Python 的 a % b 会自动处理 a < b 的情况（此时 a % b = a，然后 a, b 交换，相当于自动把大的数放在前面）。
• 每次循环，b 都会变成 a % b，而 a 变成原来的 b，变量名不需要额外定义临时变量，一行搞定。

测试一下：

# 测试几个例子
print(gcd(48, 18))   # 输出 6
print(gcd(100, 75))  # 输出 25
print(gcd(17, 19))   # 输出 1（互质）
print(gcd(0, 5))     # 输出 5 （特殊情况）

递归版本（选学）

辗转相除法也可以用递归实现，思想一样，但循环更容易理解。

def gcd_recursive(a, b):
    # 递归版本：如果b为0，返回a；否则递归调用gcd(b, a%b)
    if b == 0:
        return a
    else:
        return gcd_recursive(b, a % b)

不过递归可能受内存限制，循环版本更安全。

常见错误与注意事项

1. 忘了处理 b = 0 的情况
   如果传入的参数中有一个是0，比如 gcd(0, 5)，循环版本中 b=5≠0，第一次计算 a=0, b=0%5=0？不对，a=5, b=0%5=0？让我们手动模拟：

   • 初始 a=0, b=5
   • while b≠0: a, b = 5, 0 % 5 = 0 → 现在 a=5, b=0，循环结束，返回 a=5。
     结果正确（因为0和5的最大公约数是5）。但如果写成 a, b = b, a % b 先交换的顺序，会自动处理好，无需单独判断。

2. 循环条件写成 while a % b != 0
   初学者可能想直接判断余数，但这样会忽略 b=0 的情况，而且第一次计算前 b 可能已经为0。正确写法是判断除数 b 是否为0。

3. 混淆 a 和 b 的顺序
   虽然算法自动交换，但在写递归时容易写反参数顺序。记住：每次递归都是 gcd(b, a % b)，第一个参数是新除数，第二个是新余数。

4. 忘记取模运算
   Python 中 % 是取余，不是整除。不要写成 a // b 或 a / b。

完整可运行的示例

下面是一个完整的程序，包含输入、计算、输出，并测试多个情况：

def gcd(a, b):
    # 辗转相除法求最大公约数
    while b != 0:               # 当除数不为0时
        a, b = b, a % b         # 交替赋值：新a=原b，新b=原a%原b
    return a                    # 返回最大公约数

# 主程序：让用户输入两个整数
print("请输入两个整数，我将计算它们的最大公约数：")
num1 = int(input("第一个数: "))   # 第一个整数
num2 = int(input("第二个数: "))   # 第二个整数

result = gcd(num1, num2)
print(f"{num1} 和 {num2} 的最大公约数是 {result}")

# 测试更多例子，看看结果对不对
print("\n--- 更多测试 ---")
print(f"gcd(48, 18) = {gcd(48, 18)}")   # 应该是6
print(f"gcd(100, 75) = {gcd(100, 75)}") # 应该是25
print(f"gcd(17, 19) = {gcd(17, 19)}")   # 应该是1（互质）
print(f"gcd(0, 10) = {gcd(0, 10)}")     # 应该是10
print(f"gcd(56, 0) = {gcd(56, 0)}")     # 应该是56

把这段代码复制到 Python 环境中运行，就可以亲自体验辗转相除法的神奇了。

相关指引

• 扩展欧几里得算法：可以求出一组整数 x, y 使得 ax + by = gcd(a, b)。这在解不定方程（如鸡兔同笼）和密码学（RSA）中非常有用。
• 约分分数：有了最大公约数，就可以把分数化为最简形式（分子分母同时除以最大公约数）。
• 最小公倍数：两个数的最小公倍数 = a * b // gcd(a, b)。
• 更高级的数论算法：如快速幂、素数判断、同余方程等，都常常用到辗转相除法。

辗转相除法是数论中最基础的算法之一，虽然简单，但背后蕴含了“递归”和“迭代”的重要思想。掌握了它，你就能轻松处理许多与整数有关的问题了。