4 辗转相除法

GESP C++ 五级：辗转相除法

核心目标：理解辗转相除法（欧几里得算法）的原理与证明，掌握递归与迭代两种实现，熟练求最大公约数、最小公倍数，了解扩展欧几里得算法的基本用法，能解决分数化简、互质判断、同余方程等综合问题。
gcd(a, b) = gcd(b, a % b)，直到 b == 0，此时 a 就是最大公约数；最小公倍数用 a / gcd(a,b) * b，先除后乘防溢出；扩展欧几里得能求 ax + by = gcd(a,b) 的一组整数解。

一、考纲定位

GESP 五级初等数论模块明确要求掌握：

约数、倍数、最大公约数（GCD）、最小公倍数（LCM）
欧几里得算法（辗转相除法）
扩展欧几里得算法
同余、逆元等基础数论应用

辗转相除法是五级数论的核心工具，既是高频选择题考点，也是编程题中求 GCD/LCM、化简分数、判断互质的基础。

二、基本概念

概念	定义	示例
约数	能整除 n 的数	12 的约数：1,2,3,4,6,12
倍数	n 乘以整数得到的数	3 的倍数：3,6,9,12…
公约数	同时是两个数的约数	12 和 18 的公约数：1,2,3,6
最大公约数	公约数中最大的	gcd(12,18)=6
互质	最大公约数为 1	gcd(8,15)=1
最小公倍数	公倍数中最小的	lcm(12,18)=36

重要关系：

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

因此：

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

编程中为避免溢出，写成：

lcm = a / gcd(a, b) * b;   // 先除后乘

三、辗转相除法原理

1. 核心公式

$\gcd(a,b) = \gcd(b, a \bmod b)$

当 $b = 0$ 时：

$\gcd(a,0) = a$

2. 证明

设 $a = qb + r$ ，其中 $r = a \bmod b$ 。

若 $d$ 是 $a$ 和 $b$ 的公约数，则 $d \mid a$ ， $d \mid b$ ，所以 $d \mid (a - qb) = r$ 。
因此 $d$ 也是 $b$ 和 $r$ 的公约数。

反之，若 $d$ 是 $b$ 和 $r$ 的公约数，则 $d \mid b$ ， $d \mid r$ ，所以 $d \mid (qb + r) = a$ 。
因此 $d$ 也是 $a$ 和 $b$ 的公约数。

所以 $a,b$ 的公约数集合与 $b,r$ 的公约数集合完全相同，最大公约数自然相等。

3. 示例

求 $\gcd(48, 18)$ ：

48 % 18 = 12   → gcd(48,18) = gcd(18,12)
18 % 12 = 6    → gcd(18,12) = gcd(12,6)
12 % 6  = 0    → gcd(12,6)  = gcd(6,0) = 6
所以 gcd(48,18) = 6

四、代码实现

1. 递归版

int gcd(int a, int b) {
    if (b == 0) return a;
    return gcd(b, a % b);
}

2. 迭代版（推荐，无栈溢出风险）

int gcd(int a, int b) {
    while (b != 0) {
        int t = a % b;
        a = b;
        b = t;
    }
    return a;
}

3. 处理负数

若输入可能为负数，先取绝对值：

int gcd(int a, int b) {
    a = abs(a);
    b = abs(b);
    while (b != 0) {
        int t = a % b;
        a = b;
        b = t;
    }
    return a;
}

4. 多个数的最大公约数

int g = a[0];
for (int i = 1; i < n; i++) {
    g = gcd(g, a[i]);
}

5. 最小公倍数

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

五、复杂度分析

辗转相除法的时间复杂度为：

$O(\log \min(a,b))$

最坏情况是相邻斐波那契数，例如 $\gcd(F_n, F_{n-1})$ ，需要约 $n$ 次迭代。
空间复杂度：递归版 $O(\log n)$ ，迭代版 $O(1)$ 。

结论：辗转相除法效率极高，远优于暴力枚举。

六、扩展欧几里得算法 (了解)

扩展欧几里得用于求解二元一次不定方程：

$ax + by = \gcd(a,b)$

它返回 $\gcd(a,b)$ ，同时通过引用带回一组整数解 $x, y$ 。

1. 递归实现

long long exgcd(long long a, long long b, long long &x, long long &y) {
    if (b == 0) {
        x = 1;
        y = 0;
        return a;
    }
    long long x1, y1;
    long long d = exgcd(b, a % b, x1, y1);
    x = y1;
    y = x1 - (a / b) * y1;
    return d;
}

2. 示例

求解 $48x + 18y = \gcd(48,18)$ ：

调用 exgcd(48, 18, x, y)，得到 $d = 6$ ，一组解为 $x = -1, y = 3$ 。
验证： $48 \times (-1) + 18 \times 3 = -48 + 54 = 6$ 。

3. 应用：求逆元

若 $\gcd(a, m) = 1$ ，则 $a$ 在模 $m$ 下的逆元 $x$ 满足：

$ax \equiv 1 \pmod m$

即 $ax + my = 1$ 。用扩展欧几里得求出 $x$ ，再取模即可。

long long modInverse(long long a, long long m) {
    long long x, y;
    long long d = exgcd(a, m, x, y);
    if (d != 1) return -1;   // 不存在逆元
    return (x % m + m) % m;
}

七、常见应用

应用	方法
求最大公约数	`gcd(a, b)`
求最小公倍数	`a / gcd(a, b) * b`
判断互质	`gcd(a, b) == 1`
分数化简	分子分母同除 `gcd(分子, 分母)`
多个数 GCD	逐个求 `gcd`
多个数 LCM	逐个求 `lcm`，注意溢出
解同余方程	扩展欧几里得
求模逆元	扩展欧几里得

八、真题示例

选择题

以下代码的时间复杂度是（）。
int gcd(int a, int b) {
 while (b != 0) {
     int t = a % b;
     a = b;
     b = t;
 }
 return a;
}
A. O(1) B. O(log min(a,b)) C. O(a) D. O(a × b)
答案：B

编程题：分数化简

输入一个分数 a/b，输出化简后的分数。

#include<bits/stdc++.h>
using namespace std;

int gcd(int a, int b) {
    while (b != 0) {
        int t = a % b;
        a = b;
        b = t;
    }
    return a;
}

int main() {
    int a, b;
    cin >> a >> b;
    int g = gcd(a, b);
    cout << a / g << "/" << b / g << endl;
    return 0;
}

编程题：求两个数的最大公约数和最小公倍数

#include <iostream>
using namespace std;

long long gcd(long long a, long long b) {
    while (b != 0) {
        long long t = a % b;
        a = b;
        b = t;
    }
    return a;
}

int main() {
    long long a, b;
    cin >> a >> b;
    long long g = gcd(a, b);
    long long l = a / g * b;
    cout << g << " " << l << endl;
    return 0;
}

九、易错点汇总

递归版忘记边界条件：if (b == 0) return a; 不能漏。
迭代版循环条件写错：while (b != 0)，不是 while (a != 0)。
负数未处理：先取绝对值再求 GCD。
LCM 先乘后除导致溢出：必须 a / gcd(a,b) * b。
多个数 LCM 时溢出：每一步都先除后乘，并及时取模（若题目要求）。
扩展欧几里得赋值顺序错误：x = y1; y = x1 - (a/b)*y1; 不能写反。
求逆元时未判断互质：gcd(a,m) != 1 时逆元不存在。
混淆 GCD 与 LCM 公式：gcd × lcm = a × b，但编程中不能直接乘。

十、速查表

需求	写法
递归 GCD	`if (b==0) return a; return gcd(b, a%b);`
迭代 GCD	`while (b) { t=a%b; a=b; b=t; } return a;`
处理负数	先 `a=abs(a); b=abs(b);`
最小公倍数	`a / gcd(a,b) * b`
多个数 GCD	`g = gcd(g, a[i]);`
分数化简	分子分母同除 `gcd`
判断互质	`gcd(a,b) == 1`
扩展欧几里得	`exgcd(a,b,x,y)` 返回 `gcd`，带回 `x,y`
求逆元	`exgcd(a,m,x,y)`，若 `gcd==1`，返回 `(x%m+m)%m`
复杂度	`O(log min(a,b))`

十一、总结

辗转相除法是 GESP 五级数论模块的基石。

核心公式：gcd(a,b) = gcd(b, a % b)，直到 b == 0。
递归和迭代两种写法都要会，迭代版无栈溢出风险。
输入可能为负数时，先取绝对值。
最小公倍数用 a / gcd(a,b) * b，先除后乘防溢出。
gcd(a,b) × lcm(a,b) = a × b，这是理论关系。
多个数的 GCD 可以逐个累求。
扩展欧几里得求 ax + by = gcd(a,b) 的一组整数解。
扩展欧几里得可用于求模逆元，前提是 gcd(a,m) == 1。
辗转相除法时间复杂度 O(log min(a,b))，效率极高。
多练“求 GCD/LCM”“分数化简”“判断互质”“扩展欧几里得求逆元”四类题。