GCD 与 LCM

概念讲解

最大公约数（GCD）

两个数共有约数中最大的一个。

最小公倍数（LCM）

两个数共有倍数中最小的一个。

关系

$$\gcd(a, b) \times \text{lcm}(a, b) = a \times b$$

求解方法

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

123int gcd(int a, int b) {
    return b == 0 ? a : gcd(b, a % b);
}

时间复杂度：$O(\log \min(a, b))$

STL __gcd

12#include <algorithm>
int g = __gcd(a, b);

求 LCM

123int lcm(int a, int b) {
    return a / gcd(a, b) * b;  // 先除后乘防溢出
}

考点分析

初赛考查方式

1. 选择题： GCD/LCM 计算
2. 程序阅读： 辗转相除法
3. 编程题： GCD/LCM 应用

常见考点

• 辗转相除法
• GCD 和 LCM 关系
• 多个数的 GCD/LCM

例题精讲

例题 1：GCD

题目： 求 GCD(12, 8)。

解答：

GCD(12, 8) = GCD(8, 4) = GCD(4, 0) = 4

例题 2：LCM

题目： 求 LCM(4, 6)。

解答：

GCD(4, 6) = 2
LCM(4, 6) = 4 * 6 / 2 = 12

练习题

1. GCD(15, 10) 是多少？

GCD(15, 10) = GCD(10, 5) = GCD(5, 0) = 5

2. LCM(3, 5) 是多少？

GCD(3, 5) = 1
LCM(3, 5) = 3 * 5 / 1 = 15

3. 辗转相除法的时间复杂度是多少？

易错点

⚠️ 注意：

1. GCD(0, a) = a
2. LCM 要先除后乘防溢出
3. 辗转相除法基于数学定理
4. __gcd 在 algorithm 头文件中