CRT

Chinese Remainder Theorem. crt(a, m, b, n) computes x such that x≡ a pmod m, x≡ b pmod n. If |a| < m and |b| < n, x will obey 0 ≤ x < lcm(m, n). Assumes mn < 2^62.

Time: log(n) 7 lines Works

Needs: "euclid.h"

content/number-theory/CRT.h — Simon Lindholm

ll crt(ll a, ll m, ll b, ll n) {
	if (n > m) swap(a, b), swap(m, n);
	ll x, y, g = euclid(m, n, x, y);
	assert((a - b) % g == 0); // else no solution
	x = (b - a) % n * x % n / g * m + a;
	return x < 0 ? x + m*n/g : x;
}