欧几里得算法（辗转相除法）
一、公约数与最大公约数
1. 定义与记法
如果一个整数 \(x\) 既是整数 \(A\) 的约数，也是整数 \(B\) 的约数，那么 \(x\) 就是 \(A\) 和 \(B\) 的公约数（也叫公因数）。
例如：5 是 20 和 15 的公约数，7 是 21 和 35 的公约数。
公约数中最大的那个，称为最大公约数（Greatest Common Divisor），记作 \(\gcd(A, B)\)。
例如：24、36、60 的公约数有 2、3、4、6、12，其中最大的是 12，所以 \(\gcd(24, 36, 60) = 12\)。
2. 基本规定
理解： 任何数都是 0 的约数（因为 \(a \times 0 = 0\)），所以 \(\gcd(a, 0) = a\)。这个规定是辗转相除法递归终止的基础。
二、求 GCD 的方法
1. 暴力枚举法
思路： \(\gcd(a, b)\) 一定在 \([1, \min(a, b)]\) 之间，枚举这个区间内所有数，找最大的公约数。
从小到大枚举：
int gcd = 1;
for(int i = 1; i <= min(a, b); i++){
if(a % i == 0 && b % i == 0) gcd = i;
}
cout << gcd << endl;
从大到小枚举（优化）： 从 \(\min(a, b)\) 往下枚举，找到的第一个公约数就是最大的，直接 break。
int gcd = 1;
for(int i = min(a, b); i >= 1; i--){
if(a % i == 0 && b % i == 0){
gcd = i;
break;
}
}
cout << gcd << endl;
时间复杂度： \(O(\min(a, b))\)。当 \(a\)、\(b\) 很大时（如 \(10^9\)），会超时。
2. 更相减损法
更相减损术是中国古代《九章算术》记载的求最大公约数的算法，通过反复相减实现化简。
核心结论： 整数 \(a\) 和 \(b\)（设 \(a \geq b\)）的最大公约数，等于 \(a - b\) 和 \(b\) 的最大公约数，即：
证明： 设 \(c = \gcd(a, b)\)，则 \(a = p \times c\)，\(b = q \times c\)（\(p\)、\(q\) 互质）。
那么 \(a - b = p \times c - q \times c = (p - q) \times c\)，也是 \(c\) 的倍数，所以 \(c\) 是 \(a - b\) 和 \(b\) 的公约数。
再证 \(c\) 是最大的：假设 \(a - b\) 和 \(b\) 有更大的公约数 \(d = k \times c > c\)，则 \(d\) 也能整除 \(a = (a-b) + b\)，说明 \(a\) 和 \(b\) 有公约数 \(d > c\)，与 \(c = \gcd(a, b)\) 矛盾。所以 \(c = \gcd(a-b, b)\)。
举例： 求 \(\gcd(28, 60)\)
| 步骤 | 较大值 | 较小值 | 操作 |
|---|---|---|---|
| 初始 | 60 | 28 | — |
| 第 1 次 | 32 | 28 | \(60 - 28 = 32\) |
| 第 2 次 | 28 | 4 | \(32 - 28 = 4\) |
| 第 3 次 | 24 | 4 | \(28 - 4 = 24\) |
| 第 4 次 | 20 | 4 | \(24 - 4 = 20\) |
| 第 5 次 | 16 | 4 | \(20 - 4 = 16\) |
| 第 6 次 | 12 | 4 | \(16 - 4 = 12\) |
| 第 7 次 | 8 | 4 | \(12 - 4 = 8\) |
| 第 8 次 | 4 | 4 | \(8 - 4 = 4\)，两数相等 |
| 第 9 次 | 4 | 0 | \(4 - 4 = 0\)，最小值为0 |
一个数为0时，另一个数就是最大公约数，即 \(\gcd(28, 60) = 4\)。
代码实现：
int gcd(int a, int b){
//边界条件：若移除，则当a==0 且 b>0时，死循环
if(a == 0 || b == 0) return a + b;
//更相减损
while(a != b){
if(a > b) a -= b;
else b -= a;
}
return a;
}
问题： 当 \(a\) 远大于 \(b\) 时（如 \(a = 10^{10}\)，\(b = 1\)），需要减 \(10^{10} - 1\) 次，时间复杂度退化为 \(O(\max(a, b))\)。
3. 辗转相除法（欧几里得算法）
3.1 从更相减损法到辗转相除法
更相减损法中，\(\gcd(a, b) = \gcd(a - b, b)\)。当 \(a \gg b\) 时，要从 \(a\) 中连续减很多次 \(b\) 直到不够减，剩下的就是余数 \(a \bmod b\)。与其一次次减，不如直接用除法取余数：
这就是辗转相除法，又称欧几里得算法。
3.2 正确性证明
要证： \(\gcd(a, b) = \gcd(b, a \bmod b)\)，其中设 \(a = q \times b + r\)（\(r = a \bmod b\)，\(0 \leq r < b\)）。
证明：
设 \(d = \gcd(a, b)\)，则 \(d \mid a\) 且 \(d \mid b\)。
因为 \(r = a - q \times b\)，而 \(d \mid a\) 且 \(d \mid b\)，所以 \(d \mid r\)。因此 \(d\) 是 \(b\) 和 \(r\) 的公约数。
反过来，设 \(d' = \gcd(b, r)\)，则 \(d' \mid b\) 且 \(d' \mid r\)。因为 \(a = q \times b + r\)，所以 \(d' \mid a\)。因此 \(d'\) 是 \(a\) 和 \(b\) 的公约数。
两边互为公约数，所以 \(d = d'\)，即 \(\gcd(a, b) = \gcd(b, a \bmod b)\)。\(\blacksquare\)
3.3 时间复杂度证明
结论： \(O(\log(\max(a, b)))\)
关键： 每两次递归，较大的数至少减半。
设 \(a \ge b>0\)，序列 \(r_0=a,\ r_1=b\)，且 \(r_{i+1}=r_{i-1}\bmod r_i\)，那么有：
\((r_0, r_1) \to (r_1, r_2) \to (r_2, r_3) \to \cdots\)
于是，对于递归序列为 \(r_0, r_1, r_2, \dots\)，有：
- 若 \(r_k \leq r_{k-1} / 2\)，根据 \(r_{k+1}=r_{k-1}\bmod r_k\)，则 \(r_{k+1} < r_k \leq r_{k-1} / 2\)，较大值减半。
- 若 \(r_k > r_{k-1} / 2\)，则 \(r_{k+1} = r_{k-1} \bmod r_k = r_{k-1} - r_k < r_{k-1} / 2\)，下一步的较大值 \(r_k\) 的余数 \(r_{k+1} < r_{k-1}/2\)，也减半。
所以每两步，数至少减半，总步数不超过 \(2 \log_2(\max(a, b))\)。
3.4 举例验证
求 \(\gcd(28, 60)\)：
| 步骤 | \(a\) | \(b\) | \(a \bmod b\) | 操作 |
|---|---|---|---|---|
| 初始 | 28 | 60 | — | — |
| 第 1 次 | 60 | 28 | \(28 \bmod 60 = 28\) | \(\gcd(28, 60) = \gcd(60, 28)\) |
| 第 2 次 | 28 | \(60 \bmod 28 = 4\) | — | \(\gcd(60, 28) = \gcd(28, 4)\) |
| 第 3 次 | 4 | \(28 \bmod 4 = 0\) | — | \(\gcd(28, 4) = \gcd(4, 0)\) |
| 终止 | 4 | 0 | — | \(b = 0\)，返回 \(a = 4\) |
\(\gcd(28, 60) = 4\) ✓（与更相减损法结果一致，但只用了 3 步）
3.5 代码实现
递归写法：
int gcd(int a, int b){
if(b == 0) return a;
return gcd(b, a % b);
}
逐行解释：
| 代码 | 作用 |
|---|---|
if(b == 0) return a |
递归终止：\(b=0\) 时，\(a\) 就是 GCD |
return gcd(b, a % b) |
辗转相除：把 \(b\) 放前面，\(a \bmod b\) 放后面 |
迭代写法：
int gcd(int a, int b){
while(b != 0){
int t = a % b;
a = b;
b = t;
}
return a;
}
递归 vs 迭代： 两者逻辑完全相同。递归写法更简洁（一行核心代码），迭代写法无函数调用开销。信奥中两种都常见，递归更易记。
4. Stein 算法（更相减损法优化）
针对更相减损法在 \(a\) 远大于 \(b\) 时的低效问题，Stein 算法利用"偶数可以快速除以 2"的性质进行优化。
三条规则：
- 若 \(a\) 和 \(b\) 都是偶数，则 \(\gcd(a, b) = 2 \times \gcd(a/2, b/2)\)
- 若只有一个偶数，把偶数的因子 2 丢弃：\(\gcd(a, b) = \gcd(a/2, b)\) 或 \(\gcd(a, b/2)\)
- 若 \(a\) 和 \(b\) 都是奇数，则 \(\gcd(a, b) = \gcd(|a-b|, \min(a, b))\)
为什么快： 两个奇数相减得到偶数，下一步就可以除以 2。所以每 1～2 次操作，较大值至少减半，时间复杂度 \(O(\log(\max(a, b)))\)。
代码实现：
int gcd_stein(int a, int b){
a = abs(a);
b = abs(b);
if(a == 0 || b == 0) return a + b;
// 步骤1：提取公因子 2
int d = 0;// 记录公因子 2 的个数
while(!(a & 1) && !(b &1)) d++, a >>= 1, b >>= 1;
// 步骤2：消除各自单独的因子 2
while(!(a & 1)) a >>= 1;
while(!(b & 1)) b >>= 1;
// 步骤3：更相减损，每次减后消因子 2
while(a != b){
if(a > b) a -= b;
else b -= a;
while(!(a & 1)) a >>= 1;
while(!(b & 1)) b >>= 1;
}
return a << d;
}
位运算说明：
a & 1等价于a % 2（判断奇偶），a >>= 1等价于a /= 2（除以 2），a << d等价于a * 2^d。大整数场景下位运算比取模快得多，这是 Stein 算法存在的意义。适用场景： 大整数运算中，取模（
%）的时间开销远大于加减法和位移。Stein 算法用加减法和除以 2（位运算右移）替代取模，适合大整数 GCD。
5. 四种方法对比
| 方法 | 核心思路 | 时间复杂度 | 适用场景 |
|---|---|---|---|
| 暴力枚举法 | 枚举 \([1, \min(a,b)]\) | \(O(\min(a,b))\) | 理解概念，不用于比赛 |
| 更相减损法 | 大减小，直到相等 | \(O(\max(a,b))\) 最坏 | 历史了解，实际不用 |
| 辗转相除法 | \(\gcd(a,b) = \gcd(b, a \bmod b)\) | \(O(\log(\max(a,b)))\) | 比赛首选 |
| Stein 算法 | 更相减损 + 消因子 2 | \(O(\log(\max(a,b)))\) | 大整数（取模昂贵时） |
信奥结论： 比赛中一律用辗转相除法（欧几里得算法），代码短、速度快、不易出错。
三、公倍数与最小公倍数
1. 定义与记法
如果一个整数 \(x\) 既是 \(A\) 的倍数，也是 \(B\) 的倍数，那么 \(x\) 是 \(A\) 和 \(B\) 的公倍数。
公倍数中最小的那个，称为最小公倍数（Least Common Multiple），记作 \(\text{lcm}(A, B)\)。
例如：2、3、6 的公倍数有 6、12、24…，最小的是 6，所以 \(\text{lcm}(2, 3, 6) = 6\)。
2. 求 LCM 的方法
2.1 暴力枚举法
思路： \(\text{lcm}(a, b)\) 不超过 \(a \times b\)，在 \([1, a \times b]\) 内从小到大枚举，找第一个同时被 \(a\) 和 \(b\) 整除的数。
int lcm(int a, int b){
for(int i = 1; i <= a * b; i++){
if(i % a == 0 && i % b == 0) return i;
}
}
时间复杂度： \(O(a \times b)\)，当 \(a\)、\(b\) 较大时严重超时。
2.2 用 GCD 计算 LCM
这是最实用的方法，先求 GCD，再用公式算 LCM。
公式：
代码实现：
int gcd(int a, int b){
if(b == 0) return a;
return gcd(b, a % b);
}
int lcm(int a, int b){
return a / gcd(a, b) * b; // 先除后乘，避免溢出
}
关键技巧： 写成
a / gcd(a, b) * b，先除后乘。如果写成a * b / gcd(a, b)，a * b可能溢出（如 \(a = b = 10^9\) 时，\(a \times b = 10^{18}\) 超过int范围）。公式的推导见第四节，它来自唯一分解定理。
四、唯一分解定理与 GCD、LCM 的关系
1. 从唯一分解定理看 GCD（取小指数）
由唯一分解定理，设 \(a\) 和 \(b\) 分解质因数为（缺失的质因子指数视为 0）：
则：
理解： GCD 取每个质因数在两数中指数的较小值。只出现在一个数中的质因子，另一个数指数为 0，\(\min\) 取 0，所以不参与 GCD。
这就是质因数分解法求 GCD 的理论基础。
核心口诀：GCD 取公共质因数的小指数。
举例： \(a = 360 = 2^3 \times 3^2 \times 5^1\)，\(b = 120 = 2^3 \times 3^1 \times 5^1\)
| 质因子 | \(a\) 的指数 | \(b\) 的指数 | GCD 取小 |
|---|---|---|---|
| 2 | 3 | 3 | 3 |
| 3 | 2 | 1 | 1 |
| 5 | 1 | 1 | 1 |
代码实现：
int gcd(int a, int b){
// 对 a 分解质因数
int pa[100] = {}, cnta[100] = {}, lena = 0;
for(int i = 2; i <= a / i; i++){
if(a % i == 0){
pa[++lena] = i;
while(a % i == 0) cnta[lena]++, a /= i;
}
}
if(a > 1) pa[++lena] = a, cnta[lena] = 1;
// 对 b 分解质因数
int pb[100] = {}, cntb[100] = {}, lenb = 0;
for(int i = 2; i <= b / i; i++){
if(b % i == 0){
pb[++lenb] = i;
while(b % i == 0) cntb[lenb]++, b /= i;
}
}
if(b > 1) pb[++lenb] = b, cntb[lenb] = 1;
// 双指针合并，取公共质因数的小指数
int d = 1, i = 1, j = 1;
while(i <= lena && j <= lenb){
if(pa[i] < pb[j]) i++; // a 独有的质因子，跳过
else if(pa[i] > pb[j]) j++; // b 独有的质因子，跳过
else { // 公共质因子，取小指数
int mincnt = min(cnta[i], cntb[j]);
for(int k = 1; k <= mincnt; k++) d *= pa[i];
i++, j++;
}
}
return d;
}
注意： GCD 只取公共质因数，非公共的（只出现在一个数中的）不参与。这与 LCM 不同，下面对比。
2. 从唯一分解定理看 LCM（取大指数）
理解： LCM 取每个质因数在两数中指数的较大值。只出现在一个数中的质因子也参与，取那个非零的指数。
这就是质因数分解法求 LCM 的理论基础。
核心口诀：LCM 取所有质因数的大指数。
与 GCD 的区别： GCD 只取公共质因数的小指数；LCM 取所有质因数的大指数（包括只出现在一个数中的）。
举例： \(a = 360 = 2^3 \times 3^2 \times 5^1\)，\(b = 120 = 2^3 \times 3^1 \times 5^1\)
| 质因子 | \(a\) 的指数 | \(b\) 的指数 | LCM 取大 |
|---|---|---|---|
| 2 | 3 | 3 | 3 |
| 3 | 2 | 1 | 2 |
| 5 | 1 | 1 | 1 |
代码实现：
int lcm(int a, int b){
// 对 a 分解质因数
int pa[100] = {}, cnta[100] = {}, lena = 0;
for(int i = 2; i <= a / i; i++){
if(a % i == 0){
pa[++lena] = i;
while(a % i == 0) cnta[lena]++, a /= i;
}
}
if(a > 1) pa[++lena] = a, cnta[lena] = 1;
// 对 b 分解质因数
int pb[100] = {}, cntb[100] = {}, lenb = 0;
for(int i = 2; i <= b / i; i++){
if(b % i == 0){
pb[++lenb] = i;
while(b % i == 0) cntb[lenb]++, b /= i;
}
}
if(b > 1) pb[++lenb] = b, cntb[lenb] = 1;
// 双指针合并，取所有质因数的大指数
int d = 1, i = 1, j = 1;
while(i <= lena || j <= lenb){
if(j > lenb || (i <= lena && pa[i] < pb[j])){
// a 独有的质因子，取 a 的指数
for(int k = 1; k <= cnta[i]; k++) d *= pa[i];
i++;
} else if(i > lena || (j <= lenb && pa[i] > pb[j])){
// b 独有的质因子，取 b 的指数
for(int k = 1; k <= cntb[j]; k++) d *= pb[j];
j++;
} else {
// 公共质因子，取大指数
int maxcnt = max(cnta[i], cntb[j]);
for(int k = 1; k <= maxcnt; k++) d *= pa[i];
i++, j++;
}
}
return d;
}
易错点： LCM 的质因数分解法必须处理所有质因数，包括只出现在 \(a\) 或只出现在 \(b\) 中的。只处理公共质因数会漏掉非公共部分，导致结果偏小。
3. 核心公式：GCD × LCM = A × B
观察： 对每个质因子 \(p_i\)，\(\min(a_i, b_i)\) 和 \(\max(a_i, b_i)\) 分别取到了 \(a_i\) 和 \(b_i\) 各一次，所以：
因此：
即：
变形得：
这就是第三节中"用 GCD 计算 LCM"公式的由来。
4. 举例验证
例： \(a = 12 = 2^2 \times 3^1\)，\(b = 18 = 2^1 \times 3^2\)
| 质因子 | \(a\) 的指数 | \(b\) 的指数 | GCD 取 \(\min\) | LCM 取 \(\max\) |
|---|---|---|---|---|
| 2 | 2 | 1 | 1 | 2 |
| 3 | 1 | 2 | 1 | 2 |
验证公式：\(\gcd \times \text{lcm} = 6 \times 36 = 216\)，\(a \times b = 12 \times 18 = 216\) ✓
五、常见错误与注意事项
| 编号 | 错误 | 后果 | 改正 |
|---|---|---|---|
| E1 | LCM 写成 a * b / gcd(a,b) |
\(a \times b\) 溢出 | 写成 a / gcd(a,b) * b，先除后乘 |
| E2 | LCM 质因数分解法只处理公共质因数 | 漏掉非公共质因子，结果偏小 | 处理所有质因数，非公共的也要取大指数 |
| E3 | 辗转相除法递归终止条件写错 | 死递归或返回错误 | 终止条件是 b == 0，返回 a |
| E4 | 忘记 gcd(a, 0) = a 的规定 |
边界情况处理错误 | 记住 0 的约数是所有数，\(\gcd(a, 0) = a\) |
| E5 | 更相减损法用于 \(a\) 远大于 \(b\) | 超时（如 \(a=10^{10}, b=1\)） | 用辗转相除法或 Stein 算法 |
| E6 | GCD 和 LCM 的取指数搞反 | GCD 取了大指数，LCM 取了小指数 | GCD 取 \(\min\)，LCM 取 \(\max\) |
| E7 | 递归写法参数顺序写反 | 计算错误 | gcd(b, a % b)，余数放后面 |
口诀防混淆： GCD 是"公小"（公共质因数取小指数），LCM 是"全大"（所有质因数取大指数）。
六、方法、套路与策略小结
1. 求 GCD 的套路
- 比赛首选： 辗转相除法（欧几里得算法），一行递归搞定。
- 记忆公式： \(\gcd(a, b) = \gcd(b, a \bmod b)\)，终止于 \(b = 0\)。
- 大整数场景： 取模昂贵时用 Stein 算法（加减 + 除以 2）。
- 需要分解结果： 用质因数分解法（见第四节），顺便得到每个质因数的指数。
2. 求 LCM 的套路
- 比赛首选： 先求 GCD，再套公式 \(\text{lcm} = a / \gcd(a, b) \times b\)。
- 防溢出： 先除后乘，
a / gcd(a, b) * b。 - 口诀： LCM 取所有质因数的大指数（全大），GCD 取公共质因数的小指数（公小）。
3. 唯一分解定理与 GCD/LCM 的关系
- 桥梁： 唯一分解定理是 GCD 和 LCM 的理论基础。
- 核心公式： \(\gcd(a, b) \times \text{lcm}(a, b) = a \times b\)，知道 GCD 就能算 LCM，反之亦然。
- 指数关系： \(\min + \max = a_i + b_i\)，所以 GCD 和 LCM 的指数互补。
4. 信奥策略意识
- 复杂度意识： 辗转相除法 \(O(\log(\max(a, b)))\)，即使 \(a, b = 10^{18}\) 也只需约 60 步，极快。
- 溢出意识： 求 LCM 时先除后乘；如果结果可能超过
int，用long long。 - 代码简洁意识： 递归一行
return b ? gcd(b, a % b) : a;是最简写法。 - 验证习惯： 算完 GCD 后用唯一分解定理验证；算完 LCM 后用 \(\gcd \times \text{lcm} = a \times b\) 验证。