#IjustWantContribution
Hello Codeforces. In this post, I would like to introduce some of you to a very popular, yet maybe not fully understood technique called Chinese Remainder Theorem (CRT). I have seen many articles that present CRT in a way that lacks practical competitive programming approach (no info about how to handle overflows, how to implement it effectively, what to do when modulos are not coprime etc.) and derivation of the formulas seem like some sort of guesswork. The purpose of this article is to address this issue.
Problem and solution You are given two pairs (main goal is to solve it for t pairs) of integers (a1, n1), (a2, n2). There is no assumption that n1 and n2 are coprime. Find an integer x that satisfies
This system of congruences implies that
for some integers k1, k2. Let's equate right sides of these equations. We get a1 + n1k1 = a2 + n2k2, which is the same as n1( - k1) + n2k2 = a1 - a2. Since we know n1, n2, a1, a2, this is just linear diophantine equation. Let d = GCD(n1, n2). It divides left-hand side of the equation, so for this equation to have solutions, d must also divide right-hand side which is a1 - a2. Now, thanks to Extended Euclidean Algorithm we can find (x', y') such that n1x' + n2y' = d (by just calling (x', y') = exGCD(n1, n2)).
After multiplying both sides by 
we get 
, so 
and 
. We can now substitute k1 into x = a1 + n1k1 to get our solution: 
.
How many solutions are there? Now you may think: is this the only solution? Since we're dealing with congruences, you may guess that the answer is no. Let's say we have two different solutions x1 and x2. Now we have 
and 
, so from transitivity of congruences we get 
. Doing the same thing for n2 we get 
. These two congruences are equivalent to 
. It means that any two solutions are congruent modulo LCM(n1, n2). You can actualy check that every x given by our formula ± u * LCM(n1, n2) satisfies the original system of congruences. So there are infinitely many solutions.
Overflow issue Let's look at computational aspect of . Since the numbers can get quite big, we should perform our calculations modulo LCM(n1, n2), so if lcm = LCM(n1, n2) then 
(let's not worry about the amount of lcm's, we'll figure it out in code). But LCM(n1, n2, ..., nk) ≤ n1n2...nk, so if n1 and n2 are ≤ 109 then lcm ≤ 1018, x' ≤ 109, 
. We can calculate 
, but since it is up to 1018 and lcm is also up to 1018 the final multiplication by n1 will oveflow. How to handle this issue? Some 64bit compilers have special type int128_t that allows to store numbers up to 2127 - 1, but 64bit compilers are not too common on competitive programming contests. Let's look at a formula for lcm. We know that 
. Modulo has a very nice property that says 
, so if we take 
, 
, c = n1 we get that 
is equal to 
. Since 
, the overflow issue is solved.
Case of t congruences The last thing to consider is how to handle case of more than 2 congruences. Let's say we have t congruences 
for i = 1, 2, ..., t. We can just merge equations one by one. After merging first two congruences we get something like 
and now we can merge it in the same way with 
and so on. The complexity of this algorithm is just 
.
Code Here is a simple implementation of CRT for t congruences: LINK
Practice Easiest problem is to just implement CRT: Easy
Arkanoid from 23 Polish OI (available in English), a hard one: Arkanoid
Much easier version of Arkanoid appeard recently on CF: Billiard
Not strictly related to implementation of CRT, but checks your understanding: Remainders game
Sometimes you have to do/calculate something modulo some composite number. Then you can factorize this number, do everything you have to do, but modulo factors and finally merge the results into answer.
Thank you for reading! If you have any suggestions on how to improve this article, maybe know some good problems or spotted a mistake, feel free to write a comment.
