同余方程组c++

在C++中，可以使用扩展欧几里得算法来解决同余方程组，以下是一个实现示例：

#include <iostream>
#include <vector>
using namespace std;

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;
}

int mod_inverse(int a, int m) {
    int x, y;
    gcd(a, m, x, y);
    return (x % m + m) % m;
}

int solve_congruences(const vector<int>& a, const vector<int>& m) {
    int x = 0, M = 1;
    for (int i = 0; i < m.size(); i++) {
        int Mi = M / gcd(M, m[i]) * m[i];
        int ti = mod_inverse(Mi / m[i], m[i]);
        x = (x + a[i] * ti * Mi) % M;
        M = Mi;
    }
    return (x + M) % M;
}

int main() {
    vector<int> a = {2, 3, 2};
    vector<int> m = {3, 5, 7};
    int x = solve_congruences(a, m);
    cout << "x = " << x << endl; // 输出 x = 23
    return 0;
}

其中，“gcd”函数用于计算最大公约数和扩展欧几里得算法，它返回最大公约数d，并通过引用参数x和y返回贝祖等式ax + by = d 的解。这里使用递归实现，将x和y的顺序颠倒以便计算ti时使用。

“mod_inverse”函数用于计算a模m的逆元，即满足ax ≡ 1 (mod m)的x。

“solve_congruences”函数实现了中国剩余定理。首先计算M = m1 * m2 * ... * mn，然后对于每个同余方程，计算Mi = M / mi，以及它在模mi下的逆元ti，最后计算解x = Σ(ai * ti * Mi) (mod M)。注意到这里使用了M逆元而非mi逆元，因为后者可能不存在。

最后在主函数中输入系数和模数，调用solve_congruences函数求解同余方程组，并输出结果。