#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 (a₁, n₁), (a₂, n₂). There is no assumption that n₁ and n₂ are coprime. Find an integer x that satisfies

This system of congruences implies that

for some integers k₁, k₂. Let's equate right sides of these equations. We get a₁ + n₁k₁ = a₂ + n₂k₂, which is the same as n₁( - k₁) + n₂k₂ = a₁ - a₂. Since we know n₁, n₂, a₁, a₂, this is just linear diophantine equation. Let d = GCD(n₁, n₂). It divides left-hand side of the equation, so for this equation to have solutions, d must also divide right-hand side which is a₁ - a₂. Now, thanks to Extended Euclidean Algorithm we can find (x', y') such that n₁x' + n₂y' = d (by just calling (x', y') = exGCD(n₁, n₂)).

After multiplying both sides by we get , so and . We can now substitute k₁ into x = a₁ + n₁k₁ 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 x₁ and x₂. Now we have and , so from transitivity of congruences we get . Doing the same thing for n₂ we get . These two congruences are equivalent to . It means that any two solutions are congruent modulo LCM(n₁, n₂). You can actualy check that every x given by our formula  ± u * LCM(n₁, n₂) 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(n₁, n₂), so if lcm = LCM(n₁, n₂) then (let's not worry about the amount of lcm's, we'll figure it out in code). But LCM(n₁, n₂, ..., n_k) ≤ n₁n₂...n_k, so if n₁ and n₂ are  ≤ 10⁹ then lcm ≤ 10¹⁸, x' ≤ 10⁹, . We can calculate , but since it is up to 10¹⁸ and lcm is also up to 10¹⁸ the final multiplication by n₁ will oveflow. How to handle this issue? Some 64bit compilers have special type int128_t that allows to store numbers up to 2¹²⁷ - 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 = n₁ 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.