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

别被多变量吓到，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，直到肌肉记忆形成。