bitworld 的博客
【CSP-J初赛】最大公约数问题
bitworld 最强壮的男人 SU @ 2025-8-18 17:45:46

最大公约数问题

1. 核心概念：什么是最大公约数？

在数学中，如果一个整数 $d$ 能够整除另一个整数 $a$ （即 $a$ 除以 $d$ 余数为0），我们称 $d$ 是 $a$ 的约数（Divisor）。

例如，12的正约数有 $1, 2, 3, 4, 6, 12$ 。

如果一个整数 $d$ 同时是整数 $a$ 和整数 $b$ 的约数，那么称 $d$ 是 $a$ 和 $b$ 的公约数（Common Divisor）。

例如，12和18的正公约数有 $1, 2, 3, 6$ 。

在所有正的公约数中，最大的那一个被称为最大公约数（Greatest Common Divisor, 简称 GCD）。通常我们用 $gcd(a, b)$ 或 $(a, b)$ 来表示 $a$ 和 $b$ 的最大公约数。按照定义，最大公约数总是正数。

例如，12和18的最大公约数是6，所以 $gcd(12, 18) = 6$ 。

特殊地，我们定义 $gcd(a, 0) = |a|$ 。如果 $gcd(a, b) = 1$ ，我们称 $a$ 和 $b$ 互质（Coprime 或 Relatively Prime）。

如何计算 $gcd(a, b)$ 呢？最朴素的想法是，找出 $a$ 和 $b$ 中绝对值较小的数（不妨设为 $a$ ），然后从 $|a|$ 开始递减，逐一检查每个数是否同时是 $a$ 和 $b$ 的约数。第一个满足条件的数就是最大公约数。这种方法对于较小的数尚可，但当数字很大时，效率极低，在算法竞赛和笔试中是不可接受的。我们需要更高效的工具。

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

欧几里得算法，又称辗转相除法，是计算两个非负整数最大公约数的经典、高效算法，其历史可以追溯到古希腊。

算法原理

该算法基于一个核心定理：对于任意两个非负整数 $a$ 和 $b$ ( $b \neq 0$ )，它们的最大公约数等于 $b$ 和 $a$ 除以 $b$ 的余数 $a \pmod b$ 的最大公约数。

gcd(a, b) = gcd(b, a \pmod b)

算法的流程如下：

若 $b=0$ ，则 $a$ 就是最大公约数，即 $gcd(a, 0) = a$ 。这是算法的终止条件。
若 $b \neq 0$ ，则用 $b$ 和 $a \pmod b$ 这对新数重复上述过程。

我们以 $gcd(48, 30)$ 为例：

$gcd(48, 30) = gcd(30, 48 \pmod{30}) = gcd(30, 18)$
$gcd(30, 18) = gcd(18, 30 \pmod{18}) = gcd(18, 12)$
$gcd(18, 12) = gcd(12, 18 \pmod{12}) = gcd(12, 6)$
$gcd(12, 6) = gcd(6, 12 \pmod 6) = gcd(6, 0)$
此时第二个数为0，算法终止，结果为第一个数，即 6。

算法证明

现在我们来证明为什么 $gcd(a, b) = gcd(b, a \pmod b)$ 。设 $d = gcd(a, b)$ 。根据定义， $d$ 是 $a$ 和 $b$ 的公约数，所以 $d|a$ 且 $d|b$ 。（符号 | 表示“整除”）

我们知道，带余除法可以表示为 $a = k \cdot b + r$ ，其中 $k = \lfloor a/b \rfloor$ 是商， $r = a \pmod b$ 是余数。将上式变形为 $r = a - k \cdot b$ 。

证明 $d$ 也是 $b$ 和 $r$ 的公约数。 因为 $d|a$ 且 $d|b$ ，所以 $d$ 必定能整除它们的任意线性组合。因此 $d | (a - k \cdot b)$ ，即 $d|r$ 。既然 $d|b$ 并且 $d|r$ ，那么 $d$ 是 $b$ 和 $r$ 的一个公约数。
证明 $b$ 和 $r$ 的任意公约数也是 $a$ 和 $b$ 的公约数。 设 $c$ 是 $b$ 和 $r$ 的任意一个公约数，即 $c|b$ 且 $c|r$ 。我们考察 $a = k \cdot b + r$ 。因为 $c|b$ 和 $c|r$ ，那么 $c$ 也必定能整除它们的线性组合 $k \cdot b + r$ ，所以 $c|a$ 。既然 $c|a$ 且 $c|b$ ，那么 $c$ 也是 $a$ 和 $b$ 的一个公约数。

从第1步和第2步可知， $a$ 和 $b$ 的公约数集合与 $b$ 和 $r$ 的公约数集合是完全相同的。因此，它们的最大公约数也必然相等。

gcd(a, b) = gcd(b, a \pmod b)

证明完毕。

代码实现

递归实现 递归的逻辑直接对应了算法的数学描述。

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

// 题意概括: 计算两个非负整数a和b的最大公约数
ll gcd(ll a, ll b) {
    // b为0是递归的终止条件
    return b == 0 ? a : gcd(b, a % b);
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    ll a, b;
    cin >> a >> b;
    cout << gcd(a, b) << endl;
    return 0;
}

代码解释：函数gcd(a, b)实现了欧几里得算法。如果b是0，根据gcd(a, 0) = a返回a。否则，返回gcd(b, a % b)，问题规模被缩小。
复杂度：时间复杂度为 $O(\log \min(a, b))$ ，空间复杂度（递归栈深度）为 $O(\log \min(a, b))$ 。

迭代实现 迭代实现可以避免递归带来的额外开销，空间复杂度更优。

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

// 题意概括: 计算两个非负整数a和b的最大公约数
ll gcd(ll a, ll b) {
    while (b != 0) {
        ll r = a % b;
        a = b;
        b = r;
    }
    return a;
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    ll a, b;
    cin >> a >> b;
    cout << gcd(a, b) << endl;
    return 0;
}

代码解释：循环的条件是b不为0。在循环内部，我们计算余数r，然后将b赋值给a，将r赋值给b，实现了 (a, b) -> (b, a % b) 的转换。当循环结束时，b为0，此时的a即为所求的GCD。
复杂度：时间复杂度为 $O(\log \min(a, b))$ ，空间复杂度为 $O(1)$ 。

复杂度分析

欧几里得算法的效率极高。每一次迭代或递归，两个数的规模至少有一个会显著减小。更精确的分析由拉梅定理（Lamé's theorem）给出，它指出算法的步数不会超过两个输入数字中较小那个（以10为底）的位数的5倍。简而言之，其时间复杂度是对数级别的，即 $O(\log N)$ ，其中 $N$ 是输入数字的量级。

最小公倍数 (LCM)

最大公约数 (GCD) 与最小公倍数 (Least Common Multiple, LCM) 之间存在一个非常重要的关系。对于两个正整数 $a$ 和 $b$ ：

a \cdot b = gcd(a, b) \cdot lcm(a, b)

这个公式提供了一个计算LCM的高效方法：先用欧几里得算法求出GCD，然后通过移项计算LCM。

lcm(a, b) = \frac{a \cdot b}{gcd(a, b)}

为了防止在计算 $a \cdot b$ 时发生整数溢出（当 $a, b$ 很大时），应使用先除后乘的计算方式：

lcm(a, b) = (a / gcd(a, b)) \cdot b

3. 扩展欧几里得算法

扩展欧几里得算法（Extended Euclidean Algorithm, EXGCD）不仅计算 $gcd(a, b)$ ，还能找到一对整数 $x, y$ ，使得它们满足贝祖定理。

贝祖定理 (Bézout's Identity)

该定理指出，对于任意两个不全为零的整数 $a, b$ ，存在整数 $x, y$ ，使得：

ax + by = gcd(a, b)

例如， $gcd(48, 30) = 6$ 。扩展欧几里得算法可以找到一组解，如 $x=-1, y=2$ ，使得 $48 \cdot (-1) + 30 \cdot (2) = -48 + 60 = 6$ 。（注意解不唯一）

算法原理与实现

我们如何在求 $gcd(a,b)$ 的过程中顺便求出 $x, y$ 呢？答案依然是利用欧几里得算法的递归结构。

假设我们正在计算 $gcd(a, b)$ ，并且我们已经知道了下一层递归 $gcd(b, a \pmod b)$ 的解。也就是说，我们找到了一对 $x', y'$ 满足：

$$b \cdot x' + (a \pmod b) \cdot y' = gcd(b, a \pmod b) $$

我们的目标是利用 $x', y'$ 来表示出当前层的解 $x, y$ 。因为 $gcd(a, b) = gcd(b, a \pmod b)$ ，并且 $a \pmod b = a - \lfloor a/b \rfloor \cdot b$ ，代入上式：

$$b \cdot x' + (a - \lfloor a/b \rfloor \cdot b) \cdot y' = gcd(a, b) $$

整理这个式子，把 $a$ 和 $b$ 作为系数提取出来：

$$b \cdot x' + a \cdot y' - \lfloor a/b \rfloor \cdot b \cdot y' = gcd(a, b) $$$$a \cdot (y') + b \cdot (x' - \lfloor a/b \rfloor \cdot y') = gcd(a, b) $$

对比我们想要的最终形式 $a \cdot x + b \cdot y = gcd(a, b)$ ，可以得到：

x = y'

y = x' - \lfloor a/b \rfloor \cdot y'

这就是从下一层的解 $(x', y')$ 推导出当前层解 $(x, y)$ 的递推关系。

递归的基本情况是什么？当 $b=0$ 时， $gcd(a, 0) = a$ 。此时方程为 $a \cdot x + 0 \cdot y = a$ 。显而易见，一组解是 $x=1, y=0$ 。

代码实现 该函数通常返回GCD，并通过引用的方式修改传入的x和y。

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

// 题意概括: 求解 ax + by = gcd(a, b) 的一组整数解 (x, y)
// 函数返回 gcd(a, b)，x 和 y 通过引用返回一组特解
ll exgcd(ll a, ll b, ll &x, ll &y) {
    if (b == 0) {
        x = 1;
        y = 0;
        return a;
    }
    ll d = exgcd(b, a % b, x, y);
    ll tmp = x;
    x = y;
    y = tmp - (a / b) * y;
    return d;
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    ll a, b, x, y;
    cin >> a >> b;
    ll d = exgcd(a, b, x, y);
    cout << "gcd(" << a << ", " << b << ") = " << d << endl;
    cout << "A solution for " << a << "*x + " << b << "*y = " << d << " is: ";
    cout << "x = " << x << ", y = " << y << endl;
    return 0;
}

代码解释：exgcd(a, b, x, y) 实现了扩展欧几里得算法。在递归基b==0时，直接给出解x=1, y=0。在递归回溯时，先用d = exgcd(b, a % b, x, y)获得下一层的解，此时的x和y是x'和y'。然后根据推导出的公式x_new = y_old, y_new = x_old - (a/b)*y_old来更新x和y。注意在实现中，需要一个临时变量tmp来保存x的旧值。
复杂度：时间复杂度和空间复杂度与欧几里得算法相同。

应用：求解线性丢番图方程

形如 $ax + by = c$ 的方程被称为线性丢番图方程，其中 $a, b, c$ 是已知整数，要求解整数对 $(x, y)$ 。

这个方程有解的充要条件是 $gcd(a, b)$ 能够整除 $c$ 。

求解步骤：

计算 $d = gcd(a, b)$ 。如果 $c \pmod d \neq 0$ ，则方程无整数解。
如果 $c \pmod d = 0$ ，则先用exgcd求出 $ax' + by' = d$ 的一组解 $(x', y')$ 。
将该方程两边同时乘以 $c/d$ ，得到 $a(x' \cdot c/d) + b(y' \cdot c/d) = c$ 。
于是，原方程的一组特解是： $x_0 = x' \cdot (c/d)$ $y_0 = y' \cdot (c/d)$
方程的通解为： $x = x_0 + k \cdot (b/d)$ $y = y_0 - k \cdot (a/d)$ 其中 $k$ 为任意整数。

应用：求解模线性方程与乘法逆元

求解形如 $ax \equiv c \pmod m$ 的模线性方程。该方程等价于 $ax - c = my$ 对于某个整数 $y$ ，变形即 $ax - my = c$ 。这是一个线性丢番图方程。令 $b = -m$ ，就化为 $ax+by=c$ 的形式，可按上节方法求解。

一个特别重要且常见的特例是求模乘法逆元（Modular Multiplicative Inverse）。求解 $ax \equiv 1 \pmod m$ 。这要求找到一个整数 $x$ 使得 $ax$ 与 1 模 $m$ 同余。这个 $x$ 称为 $a$ 关于模 $m$ 的逆元。

根据丢番图方程的理论，该方程有解的充要条件是 $gcd(a, m)$ 整除 1。由于 $gcd(a, m)$ 是正整数，这意味着 $gcd(a, m) = 1$ ，即 $a$ 和 $m$ 必须互质。

当 $a$ 和 $m$ 互质时，我们可以用exgcd求解方程 $ax + my = 1$ 。得到的解 $x$ 就是 $a$ 模 $m$ 的一个逆元。通常我们希望得到一个在 $[1, m-1]$ 范围内的解，可以通过 (x % m + m) % m 操作将解调整到该范围。

4. 其他GCD算法：二进制GCD与更相减损术

除了辗转相除法，还存在其他计算GCD的算法，它们在特定场景下有其优势。

更相减损术

这是中国古代《九章算术》中记载的一种求GCD方法，其原理是：对于任意两个正整数 $a, b$ ( $a > b$ )，有 $gcd(a, b) = gcd(a-b, b)$ 。通过反复用较大数减去较小数，最终会得到两个相等的数，这个数就是GCD。例如，$gcd(48, 30) = gcd(18, 30) = gcd(18, 12) = gcd(6, 12) = gcd(6, 6) = 6$。这个方法只用减法，但当两数差距很大时，需要进行大量减法，效率低于欧几里得算法。

二进制GCD算法 (Stein's Algorithm)

该算法完全避免了（较慢的）乘除法和取模运算，只使用（较快的）位移（乘除2）、减法和比较运算，在某些计算机体系结构上效率更高。其原理基于以下几点：

如果 $a, b$ 均为偶数，则 $gcd(a, b) = 2 \cdot gcd(a/2, b/2)$ 。
如果 $a$ 为偶数， $b$ 为奇数，则 $gcd(a, b) = gcd(a/2, b)$ 。
如果 $a, b$ 均为奇数，且 $a>b$ ，则 $gcd(a, b) = gcd(a-b, b)$ 。由于 $a-b$ 是偶数，下一步可以归约到情况2。为了加速，可以直接变为 $gcd((a-b)/2, b)$ 。

通过结合这些规则，可以设计出一个高效的递归或迭代算法。

5. 笔试题实战演练

选择题

$gcd(312, 221)$ 的值是？ A. 1 B. 13 C. 17 D. 29

解析： $gcd(312, 221) = gcd(221, 312 \pmod{221}) = gcd(221, 91)$ $gcd(221, 91) = gcd(91, 221 \pmod{91}) = gcd(91, 39)$ $gcd(91, 39) = gcd(39, 91 \pmod{39}) = gcd(39, 13)$ $gcd(39, 13) = gcd(13, 39 \pmod{13}) = gcd(13, 0)$ 结果是13。 答案：B

选择题：线性丢番图方程 $14x + 35y = 48$ 的整数解情况是？ A. 有唯一解 B. 无整数解 C. 有无穷多解 D. 有两组解

解析：方程 $ax+by=c$ 有解的充要条件是 $gcd(a, b)|c$ 。这里 $a=14, b=35$ 。计算 $gcd(14, 35)$ 。 $gcd(35, 14) = gcd(14, 35 \pmod {14}) = gcd(14, 7) = gcd(7, 0) = 7$。我们需要检查 7 是否能整除 48。 $48 \div 7$ 余 6，不能整除。因此，该方程无整数解。 答案：B

判断题

如果 $d = gcd(a, b)$ ，则 $gcd(a/d, b/d) = 1$ 。

解析：正确。这是GCD的一个基本性质。假设 $gcd(a/d, b/d) = k > 1$ 。那么 $k|(a/d)$ 且 $k|(b/d)$ 。这意味着存在整数 $m, n$ 使得 $a/d = km$ 且 $b/d = kn$ 。于是 $a=kdm, b=kdn$ 。这表明 $kd$ 同时是 $a$ 和 $b$ 的公约数。由于 $k>1, d \ge 1$ , 所以 $kd > d$ 。这与 $d$ 是 $a, b$ 的最大公约数矛盾。因此假设不成立，必定有 $k=1$ 。
欧几里得算法的时间复杂度是输入数字大小的线性函数。

解析：错误。如前所述，欧几里得算法的时间复杂度是对数级别的，即 $O(\log \min(a, b))$ ，效率非常高，远快于线性。

程序阅读题

阅读下列C++代码，写出其对输入 48 18 的输出结果。
```
#include<iostream>
using namespace std;
int f(int a, int b) {
    if (a == 0) return b;
    if (b == 0) return a;
    if (a % 2 == 0 && b % 2 == 0) return 2 * f(a / 2, b / 2);
    if (a % 2 == 0) return f(a / 2, b);
    if (b % 2 == 0) return f(a, b / 2);
    if (a > b) return f((a - b) / 2, b);
    return f((b - a) / 2, a);
}
int main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int a = 48, b = 18;
    cout << f(a, b) << endl;
    return 0;
}
```
解析：该代码实现了二进制GCD算法（Stein's Algorithm）。我们来追踪执行流程：
1. f(48, 18): a和b都是偶数。返回 2 * f(24, 9)。
2. f(24, 9): a是偶数，b是奇数。返回 f(12, 9)。
3. f(12, 9): a是偶数，b是奇数。返回 f(6, 9)。
4. f(6, 9): a是偶数，b是奇数。返回 f(3, 9)。
5. f(3, 9): a和b都是奇数，a < b。返回 f((9 - 3) / 2, 3)，即 f(3, 3)。
6. f(3, 3): 此时a和b都是奇数，a不大于b。代码会进入最后一个return语句，f((3-3)/2, 3) 即 f(0, 3)。
7. f(0, 3): a为0，返回b，即3。最终结果是 2 * 3 = 6。 输出：6

程序填空题

补全下面的C++代码，使其能够计算并输出 $a$ 和 $b$ 的最小公倍数（LCM）。

#include<iostream>
using namespace std;
using ll = long long;

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

ll lcm(ll a, ll b) {
    if (a == 0 || b == 0) return 0;
    // ---- BEGIN ----
    ________________________
    // ---- END ----
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    ll a, b;
    cin >> a >> b;
    cout << lcm(a, b) << endl;
    return 0;
}

解析：根据公式 $lcm(a, b) = (a \cdot b) / gcd(a, b)$ 。为了防止中间结果 $a \cdot b$ 溢出，最好写成先除后乘的形式。答案：return (a / gcd(a, b)) * b;

补全下面的扩展欧几里得算法，求解 $ax+by=gcd(a,b)$ 。
```
#include<iostream>
using namespace std;
using ll = long long;

ll exgcd(ll a, ll b, ll &x, ll &y) {
    if (b == 0) {
        x = 1;
        y = 0;
        return a;
    }
    ll d = exgcd(b, a % b, x, y);
    ll tmp = x;
    // ---- BEGIN ----
    ________________________
    ________________________
    // ---- END ----
    return d;
}
```
解析：这里需要填入从下一层递归解 $(x', y')$ （在代码中就是调用返回后的 x 和 y）计算当前层解的递推关系。递推关系为 $x_{new} = y_{old}$ 和 $y_{new} = x_{old} - (a/b) \cdot y_{old}$ 。在代码中，调用 exgcd 后，x 和 y 的值是下一层的解。我们需要先用一个临时变量 tmp 保存 x 的旧值，因为它在计算新 y 时需要用到。答案：
```
x = y;
y = tmp - (a / b) * y;
```

【CSP-J初赛】最大公约数问题