CodeArchive ChineseRemainderTheorem
From Ubcacm
Chinese Remainder Theorem
This can be applied to a set of 2 modular equations.
We need extended GCD for this code to work.
typedef long long INT;
// z % a1 == b1
// z % a2 == b2
// a1,a2 > 0, b1,b2 >= 0, a1 > b1, a2 > b2
// Return true if possible, false otherwise
bool chin_rem(INT a1, INT b1, INT a2, INT b2, INT& a, INT& b) {
INT X1, X2;
INT d = egcd(a1, a2, X1, X2);
if ( (b1 % d) != (b2 % d) ) return false;
a = a1 / d * a2;
b = (X1*a1*(b2/d) + X2*a2*(b1/d) + (b1%d))%a;
return true;
}
-- Main.MatthewChan - 24 Mar 2006
