c++实现拓展欧几里得的完整代码

拓展欧几里得算法（Extended Euclidean Algorithm）是求解不定方程 $ax+by=\gcd(a,b)$ 的一种有效方法，其中 $a,b$ 为正整数，$\gcd(a,b)$ 表示 $a$ 和 $b$ 的最大公约数。该算法可以用于求解线性同余方程 $ax \equiv b \pmod{m}$ 的解集，其中 $m$ 为正整数。

下面是 C++ 实现拓展欧几里得算法的完整代码：

#include <iostream>
using namespace std;

// 求 a 和 b 的最大公约数，并返回其值
int gcd(int a, int b, int &x, int &y) {
    if (b == 0) {
        x = 1;
        y = 0;
        return a;
    }
    int d = gcd(b, a % b, y, x);
    y -= a / b * x;
    return d;
}

// 解线性同余方程 ax ≡ b (mod m)，并返回其解集
void solve(int a, int b, int m) {
    int x, y;
    int d = gcd(a, m, x, y);
    if (b % d == 0) {
        int x0 = (long long)x * (b / d) % m;
        for (int i = 0; i < d; i++) {
            int ans = (x0 + i * (m / d) % m + m) % m;
            cout << ans << " ";
        }
        cout << endl;
    } else {
        cout << "No solution" << endl;
    }
}

int main() {
    int a, b, m;
    cin >> a >> b >> m;
    solve(a, b, m);
    return 0;
}

该代码中，函数 `gcd` 实现了求解不定方程 $ax+by=\gcd(a,b)$ 的过程，并返回其最大公约数 $\gcd(a,b)$。函数 `solve` 则利用 `gcd` 求解线性同余方程 $ax \equiv b \pmod{m}$ 的解集，并输出结果。如果无解，则输出 "No solution"。

需要注意的是，在实现过程中要注意数据类型的选择，例如在计算 $x0$ 的时候需要使用 long long 类型来避免溢出。