C++ 数论进阶：裴蜀定理与扩展欧几里得算法实战

C++ 数论进阶：裴蜀定理与扩展欧几里得算法实战

数论在信息学竞赛中是个绕不开的大山，尤其是涉及不定方程和模运算的部分。今天咱们不整虚的，直接聊聊裴蜀定理（Bézout's identity）以及它背后的核心工具——扩展欧几里得算法。

学习目标

1. 理清脉络：搞懂同余、裴蜀定理、扩展欧几里得、乘法逆元之间的逻辑链条。
2. 掌握核心：能熟练手写扩展欧几里得算法，解决线性不定方程。
3. 实战应用：面对 CSP-S 级别的数论模板题，知道怎么快速建模。

核心概念回顾

裴蜀定理其实就一句话：对于任意整数 $a, b$，存在整数 $x, y$ 使得 $ax + by = d$，其中 $d = \gcd(a, b)$。而且，$d$ 是所有形如 $ax+by$ 的整数中最小的正整数。

这意味着什么？意味着只要你能算出最大公约数，你就知道这个线性组合的最小值是多少。而求最大公约数的经典方法就是欧几里得算法，那如果要找出具体的 $x, y$ 呢？这时候就需要扩展欧几里得算法（exgcd）了。

代码实现与解析

写 exgcd 的时候，很多人容易在递归边界或者符号上栽跟头。这里给个标准写法，顺便解释一下为什么这么写。

// 扩展欧几里得算法
// 返回 gcd(a, b)，同时更新 x, y 使得 ax + by = gcd(a, b)
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 d = exgcd(b, a % b, y, x);
    y -= a / b * x;
    return d;
}

注意看递归调用那里 exgcd(b, a % b, y, x)，这里直接把 x 和 y 传反了。这是为了利用数学推导中的代换关系，省去了中间变量。实际运行时会发现，当 $b=0$ 时，$a\cdot1 + 0\cdot0 = a$，这就是初始状态。回溯过程中通过 $y -= a/b*x$ 来修正系数。

实战案例：P4549 裴蜀定理

题目背景

给定一个包含 $n$ 个整数的序列 $a_1, a_2, \dots, a_n$。我们需要找到一个最小的正整数 $k$，使得存在整数 $x_1, x_2, \dots, x_n$ 满足 $\sum_{i=1}^n a_i x_i = k$。

这其实就是裴蜀定理的多变量推广。结论很简单：这个最小的正整数 $k$ 就是所有 $a_i$ 的最大公约数。如果所有数都是 0，那答案就是 0。

解题思路

别被多变量吓到，GCD 的性质是结合的。$\gcd(a, b, c) = \gcd(\gcd(a, b), c)$。所以我们可以用循环累加的方式求整个序列的 GCD。

参考代码

#include <iostream>
#include <vector>
#include <numeric>

using namespace std;

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 d = exgcd(b, a % b, y, x);
    y -= a / b * x;
    return d;
}

int main() {
    int n;
    if (!(cin >> n)) return 0;
    
    vector<long long> a(n);
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }

    // 特殊情况处理：如果所有数都是 0
    bool all_zero = true;
    for (long long val : a) {
        if (val != 0) {
            all_zero = false;
            break;
        }
    }
    
    if (all_zero) {
        cout << 0 << endl;
        return 0;
    }

    // 计算所有数的最大公约数
    long long result = 0;
    for (long long val : a) {
        result = exgcd(result, val, x, y); // 这里的 x, y 不需要关心具体值，只需要结果
    }
    
    // 输出绝对值，因为 GCD 定义为正
    cout << abs(result) << endl;
    
    return 0;
}

细节提醒

1. 数据类型：输入可能很大，记得用 long long，虽然 P4549 的数据范围通常不会爆 int，但养成习惯比较好。
2. 全零情况：很多选手会忽略 $a_i$ 全为 0 的情况，导致 WA。上面代码里专门加了判断。
3. 负数处理：GCD 的结果应该是正的，所以最后取个 abs() 更稳妥。

总结

裴蜀定理的核心在于理解'线性组合'与'最大公约数'的关系。在实际做题时，看到类似 $ax + by = c$ 的不定方程，或者多变量线性组合求极值的问题，第一时间反应出 GCD 就能省下大量思考时间。配合扩展欧几里得算法，这类数论题基本就拿下大半了。

下次遇到分数模运算或者乘法逆元，你会发现它们本质上还是这套逻辑的延伸。保持手感，多敲几遍 exgcd，直到肌肉记忆形成。