Extended GCD & CRT
O(log min(a, b))Extended Euclid finds x, y with ax + by = gcd(a, b), which gives modular inverses for non-prime moduli and solves linear Diophantine equations. CRT combines two congruences x ≡ r1 (mod m1), x ≡ r2 (mod m2) into one, handling non-coprime moduli.
// use it on
Kattis: Chinese Remainder ↗
Solve the two-congruence system directly with the crt function; huge moduli are why the C++ version multiplies through __int128.
// the code
// g = gcd(a, b) and x, y with a*x + b*y = g
long long ext_gcd(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, g = ext_gcd(b, a % b, x1, y1);
x = y1;
y = x1 - (a / b) * y1;
return g;
}
// combine x = r1 (mod m1) and x = r2 (mod m2)
// returns {x, lcm}, or {-1, -1} if incompatible
pair<long long, long long> crt(long long r1, long long m1,
long long r2, long long m2) {
long long x, y;
long long g = ext_gcd(m1, m2, x, y);
if ((r2 - r1) % g != 0) return {-1, -1};
long long lcm = m1 / g * m2;
long long mg = m2 / g;
long long t = (__int128)((r2 - r1) / g % mg) * (x % mg) % mg;
if (t < 0) t += mg;
long long res = (long long)(((__int128)m1 * t + r1) % lcm);
if (res < 0) res += lcm;
return {res, lcm};
}