Chinese Remainder Theorem: Solving Modular Equations

x ≡ a_1 (mod m_1)
x ≡ a_2 (mod m_2)
...
x ≡ a_k (mod m_k)

M = product of all m_i
For each i:
    M_i = M / m_i
    y_i = inverse of M_i mod m_i  (extended GCD)
    contribution_i = a_i * M_i * y_i
x = sum of contribution_i, mod M

def ext_gcd(a, b):
    if b == 0: return a, 1, 0
    g, x, y = ext_gcd(b, a % b)
    return g, y, x - (a // b) * y

def crt(remainders, moduli):
    M = 1
    for m in moduli:
        M *= m
    x = 0
    for a, m in zip(remainders, moduli):
        Mi = M // m
        _, yi, _ = ext_gcd(Mi, m)
        x = (x + a * Mi * yi) % M
    return x

# Example: x ≡ 2 (mod 3), x ≡ 3 (mod 5), x ≡ 2 (mod 7)
print(crt([2, 3, 2], [3, 5, 7]))  # 23

# Generalized CRT (moduli not necessarily coprime)
def crt_general(a1, m1, a2, m2):
    g, p, q = ext_gcd(m1, m2)
    if (a2 - a1) % g != 0:
        return None, None  # no solution
    lcm = m1 // g * m2
    x = (a1 + m1 * ((a2 - a1) // g * p % (m2 // g))) % lcm
    return x, lcm

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pll;

ll extgcd(ll a, ll b, ll& x, ll& y) {
    if (!b) { x=1; y=0; return a; }
    ll x1, y1;
    ll g = extgcd(b, a%b, x1, y1);
    x = y1; y = x1 - a/b*y1;
    return g;
}

// Returns {x, M} such that x ≡ a_i (mod m_i)
pll crt(vector<ll> a, vector<ll> m) {
    ll M = 1, x = 0;
    for (auto mi : m) M *= mi;
    for (int i = 0; i < (int)a.size(); i++) {
        ll Mi = M / m[i];
        ll p, q;
        extgcd(Mi, m[i], p, q);
        x = (x + a[i] * Mi % M * ((p % m[i] + m[i]) % m[i])) % M;
    }
    return {x, M};
}