CRT solves systems like x ≡ a_i (mod m_i) when moduli are pairwise coprime. The solution is unique modulo M = product(m_i). Implementation uses modular inverses, usually from extended Euclid.
long long egcd(long long a, long long b, long long& x, long long& y) {
if (b == 0) { x = 1; y = 0; return a; }
long long x1, y1;
long long g = egcd(b, a % b, x1, y1);
x = y1;
y = x1 - y1 * (a / b);
return g;
}
long long modInv(long long a, long long m) {
long long x, y;
egcd(a, m, x, y);
x %= m; if (x < 0) x += m;
return x;
}
long long crt(vector<long long>& a, vector<long long>& m) {
long long M = 1;
for (auto v : m) M *= v;
long long ans = 0;
for (int i = 0; i < (int)a.size(); i++) {
long long Mi = M / m[i];
ans = (ans + a[i] * Mi % M * modInv(Mi, m[i]) % M) % M;
}
return ans;
}Requires pairwise coprime moduli for the classic theorem form.
Build M, then each term uses Mi = M/mi and inverse of Mi modulo mi.
Final answer is unique modulo M.
Quiz coming soon for this algorithm.