**#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*_{1}, *n*_{1}), (*a*_{2}, *n*_{2}). **There is no assumption that n_{1} and n_{2} are coprime**. Find an integer

*x*that satisfies

This system of congruences implies that

for some integers *k*_{1}, *k*_{2}. Let's equate right sides of these equations. We get *a*_{1} + *n*_{1}*k*_{1} = *a*_{2} + *n*_{2}*k*_{2}, which is the same as *n*_{1}( - *k*_{1}) + *n*_{2}*k*_{2} = *a*_{1} - *a*_{2}. Since we know *n*_{1}, *n*_{2}, *a*_{1}, *a*_{2}, this is just linear diophantine equation. Let *d* = *GCD*(*n*_{1}, *n*_{2}). 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*_{1} - *a*_{2}. Now, thanks to Extended Euclidean Algorithm we can find (*x*', *y*') such that *n*_{1}*x*' + *n*_{2}*y*' = *d* (by just calling (*x*', *y*') = *exGCD*(*n*_{1}, *n*_{2})).

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

Nice blog! You can also mention the complexity of CRT.

Wow, I've never thought that chinese remainder theorem is so intuitive and straightforward.

Can anyone provide some more problems on CRT as I'm not able to find them