剩余定理最简单的方法

def extended_gcd(a, b):
    if a == 0:
        return b, 0, 1
    else:
        g, y, x = extended_gcd(b % a, a)
        return g, x - (b // a)  y, y
def modinv(a, m):
    g, x, y = extended_gcd(a, m)
    if g != 1:
        raise Exception('Modular inverse does not exist')
    else:
        return (x % m + m) % m
def chinese_remainder_theorem(remainders, moduli):
    # 检查模数是否两两互质
    for i in range(len(moduli)):
        for j in range(i + 1, len(moduli)):
            if math.gcd(moduli[i], moduli[j]) != 1:
                raise Exception('Moduli are not pairwise coprime')
    M = 1
    for m in moduli:
        M = m
    x = 0
    for i in range(len(moduli)):
        M_i = M // moduli[i]
        y_i = modinv(M_i, moduli[i])
        x += remainders[i]  M_i  y_i
    return x % M
示例：x ≡ 2 (mod 3), x ≡ 3 (mod 5), x ≡ 2 (mod 7)
remainders = [2, 3, 2]
moduli = [3, 5, 7]
print("解为:", chinese_remainder_theorem(remainders, moduli))
        

#include 
#include 
using namespace std;
typedef long long ll;
ll gcd(ll a, ll b) {
    return b == 0 ? a : gcd(b, a % b);
}
ll modinv(ll a, ll m) {
    ll m0 = m, t, q;
    ll x0 = 0, x1 = 1;
    if (m == 1) return 0;
    while (a > 1) {
        q = a / m;
        t = m;
        m = a % m, a = t;
        t = x0;
        x0 = x1 - q  x0;
        x1 = t;
    }
    if (x1 < 0) x1 += m0;
    return x1;
}
ll chinese_remainder_theorem(vector& a, vector& m) {
    ll M = 1;
    for (ll mi : m) M = mi;
    ll x = 0;
    for (size_t i = 0; i < a.size(); ++i) {
        ll Mi = M / m[i];
        x = (x + a[i]  Mi % M  modinv(Mi, m[i]) % M) % M;
    }
    return x;
}
int main() {
    vector a = {2, 3, 2};
    vector m = {3, 5, 7};
    cout << "解为: " << chinese_remainder_theorem(a, m) << endl;
    return 0;
}