中国剩余定理简单例题：从古代智慧到现代算法

def extended_gcd(a, b):
    if a == 0:
        return b, 0, 1
    gcd, x1, y1 = extended_gcd(b % a, a)
    x = y1 - (b // a)  x1
    y = x1
    return gcd, x, y
def inverse(a, m):
    g, x, _ = extended_gcd(a, m)
    if g != 1:
        raise Exception('Modular inverse does not exist')
    return (x % m + m) % m
def chinese_remainder_theorem(n_list, a_list):
    """
    n_list: 模数列表 [m1, m2, ...]
    a_list: 余数列表 [a1, a2, ...]
    """
    M = 1
    for n in n_list:
        M = n
    result = 0
    for n_i, a_i in zip(n_list, a_list):
        M_i = M // n_i
        t_i = inverse(M_i, n_i)
        result += a_i  M_i  t_i
    return result % M
测试：韩信点兵
print(chinese_remainder_theorem([3, 5, 7], [2, 3, 2])) # 输出 23

#include <iostream>
using namespace std;
typedef long long ll;
ll exgcd(ll a, ll b, ll &x, ll &y) {
    if (!b) { x = 1; y = 0; return a; }
    ll d = exgcd(b, a % b, y, x);
    y -= a / b  x;
    return d;
}
ll inv(ll a, ll m) {
    ll x, y;
    exgcd(a, m, x, y);
    return (x % m + m) % m;
}
ll crt(vector<ll> &n, vector<ll> &a) {
    ll M = 1;
    for (auto val : n) M = val;
    ll res = 0;
    for (int i = 0; i < n.size(); ++i) {
        ll Mi = M / n[i];
        res = (res + a[i]  Mi % M  inv(Mi, n[i]) % M) % M;
    }
    return res;
}