最大公约数与最小公倍数 - CSP-J | C++ & Algorithm 编程研习社

最大公约数和最小公倍数：两个数的“公共因子”与“公共倍数”

今天我们来聊一对数学好兄弟——最大公约数（GCD）和最小公倍数（LCM）。
它们就像两个班级共同拥有的假期：最大公约数是最长的公共假期（相同因子中的最大者），最小公倍数则是下一次两个班同时放假的日子（相同倍数中的最小者）。
在编程竞赛和生活中，这两个概念经常一起出现，比如分糖果、安排班车、计算路灯同时亮起的时刻。掌握了它们，很多“周期”问题都会迎刃而解。

一、第一次见面：最大公约数（GCD）

最大公约数，英文叫 Greatest Common Divisor（GCD），是指两个或多个整数共有的因数中最大的那个。

因数的概念：一个整数能整除另一个整数，比如 12 ÷ 3 = 4，3 就是 12 的因数（也叫约数）。
公因数：两个数都有的因数。
最大公因数：公因数中最大的那一个。

例子：12 和 18

12 的因数：1, 2, 3, 4, 6, 12
18 的因数：1, 2, 3, 6, 9, 18
公共因数：1, 2, 3, 6
最大的是 6，所以 gcd(12, 18) = 6。

生活场景：你有 12 颗奶糖和 18 颗水果糖，想平均分给几个好朋友，每人拿到同样多的奶糖和水果糖，最多可以分给几个人？
答案就是 gcd(12, 18) = 6，每人得到 2 颗奶糖和 3 颗水果糖。

二、再来认识：最小公倍数（LCM）

最小公倍数，英文叫 Least Common Multiple（LCM），是指两个或多个整数共有的倍数中最小的那个（0 除外）。

倍数的概念：一个整数乘以自然数得到的结果，比如 12 的倍数有 12, 24, 36, 48, …
公倍数：两个数共有的倍数。
最小公倍数：公倍数中最小的正数。

例子：12 和 18

12 的倍数：12, 24, 36, 48, 60, …
18 的倍数：18, 36, 54, 72, …
公共倍数：36, 72, …
最小的是 36，所以 lcm(12, 18) = 36。

生活场景：红绿灯 A 每 12 秒变一次色，红绿灯 B 每 18 秒变一次色。它们同时变绿色之后，再过多少秒会再次同时变绿？
答案就是 lcm(12, 18) = 36 秒。

三、Python 直接计算：`math` 模块帮你搞定

Python 的 math 模块里已经提供了 gcd 函数，可以直接用。
至于最小公倍数，没有现成的函数，但有一个重要公式：

lcm(a, b) = a × b ÷ gcd(a, b)

注意：要先用整数乘法再做整除，避免出现小数。

import math

def lcm(a, b):
    """
    返回 a 和 b 的最小公倍数
    """
    return a * b // math.gcd(a, b)  # 先乘后整除，结果一定是整数

# 测试
num1 = 12   # 第一个数
num2 = 18   # 第二个数
print("gcd =", math.gcd(num1, num2))  # 输出 6
print("lcm =", lcm(num1, num2))       # 输出 36

四、自己动手写：辗转相除法（欧几里得算法）

虽然 math.gcd 很方便，但竞赛中有时需要自己实现 GCD。最经典的方法就是辗转相除法（也叫欧几里得算法）。

原理：两个整数 a 和 b（a ≥ b），它们的最大公约数等于 b 和 a % b 的最大公约数。重复这个操作，直到余数为 0，此时除的那个数就是答案。

例子：求 24 和 36 的 gcd

36 ÷ 24 = 1 余 12 → 问题变成求 gcd(24, 12)
24 ÷ 12 = 2 余 0 → 余数为 0，所以 gcd 是 12

代码实现（递归和循环两种写法）：

# 递归写法
def gcd_recursive(x, y):
    """
    辗转相除法（递归）
    """
    if y == 0:
        return x            # 当 y 为 0 时，x 就是最大公约数
    return gcd_recursive(y, x % y)  # 交换位置并取余

# 循环写法（更推荐，不担心递归深度）
def gcd_loop(x, y):
    """
    辗转相除法（循环）
    """
    while y != 0:           # 直到 y 变成 0
        x, y = y, x % y     # 同时更新：x 变成 y，y 变成 x 除以 y 的余数
    return x                # 最终的 x 就是最大公约数

# 测试
print(gcd_recursive(12, 18))  # 输出 6
print(gcd_loop(12, 18))       # 输出 6

有了自己写的 gcd，也可以实现 lcm：

def lcm_custom(a, b):
    return a * b // gcd_loop(a, b)  # 使用上面自定义的 gcd

五、生活中的更多例子

分铅笔和橡皮：24 支铅笔和 36 块橡皮分给小朋友，每人得到的铅笔和橡皮一样多，最多分给多少人？
答：gcd(24, 36) = 12，每人 2 支铅笔、3 块橡皮。
买零食凑整：A 零食每袋 6 元，B 零食每袋 10 元，小明想花同样多的钱买两种零食，最少要花多少钱？
答：找 6 和 10 的最小公倍数 = lcm(6, 10) = 30 元（可以买 5 袋 A 或 3 袋 B）。
考试时间周期：数学考试每 3 天一次，英语考试每 5 天一次，今天两门都考了，下一次同时考是几天后？
答：lcm(3, 5) = 15 天后。

六、新手容易犯的错误

忘记 import math：直接写 math.gcd() 会报错，需要先 import math。
lcm 公式写成 a * b / math.gcd(a, b)：/ 会得到浮点数（比如 6.0），后续判断可能出错，建议用 // 整数除法。
参数顺序误以为必须 a ≥ b：gcd 函数内部会自动处理，即使 gcd(18, 12) 也能得到正确结果 6，但自己写循环时要注意迭代条件。
未考虑 0：gcd(0, a) 的结果是 a，lcm(0, a) 一般定义为 0（实际很少用到）。竞赛中题目通常保证输入为正整数。
混淆 gcd 和 lcm 的含义：分糖果用 gcd，求下次同时发生用 lcm，多想想场景就不容易记反。

七、完整可运行的示例代码

下面是一个完整程序，用户输入两个正整数，输出它们的 gcd 和 lcm：

import math

def lcm(a, b):
    """
    计算 a 和 b 的最小公倍数
    """
    return a * b // math.gcd(a, b)  # 利用公式

# 输入两个数
num1 = int(input("请输入第一个正整数："))  # 第一个数
num2 = int(input("请输入第二个正整数："))  # 第二个数

# 计算并输出
g = math.gcd(num1, num2)       # 最大公约数
l = lcm(num1, num2)            # 最小公倍数

print("最大公约数 (GCD) =", g)   # 输出 gcd
print("最小公倍数 (LCM) =", l)   # 输出 lcm

运行示例：

请输入第一个正整数：12
请输入第二个正整数：18
最大公约数 (GCD) = 6
最小公倍数 (LCM) = 36

八、相关知识点指引

扩展欧几里得算法：不仅能求 gcd，还能找到满足 ax + by = gcd(a,b) 的整数解，在解模方程时很有用。
分数化简：约分就是分子分母同时除以它们的 gcd。
多个数的 gcd 与 lcm：可以两两逐步求出，比如 gcd(a,b,c) = gcd(gcd(a,b), c)，lcm 同理。
质因数分解法：另一种手算 gcd/lcm 的方法，适合小数字，但不适合编程（大数分解困难）。
CSP-J 数论常用技巧：在循环中求一组数的 gcd，或者利用 lcm 解决周期问题（比如“第几天同时休息”）。

掌握 gcd 和 lcm，就像掌握了一把钥匙，很多看似复杂的数学问题都能轻松打开。多动手写两次代码，你就是下一个数论小能手！

例题精讲