Chinese Remainder Theorem

A linear congruence can be displayed as $$ ax \equiv b (\text{mod } m ) $$ By definition of congruence, $ ax \equiv b (\text{mod } m ) $ iff $ax - b$ is disible by $m$. According to Wikipedia, the earliest known statement of the Chinese Remainder Theorem is by the Chinese mathematician Sun-tzu in the Sun-tzu Suan-ching in the 3rd century AD. $$ 今有物不知其數，三三數之剩二，五五數之剩三，七七數之剩二，問物幾何？ $$ We can rewrite the above statement into below congruence equations. $$ x \equiv 2 (\text{mod } 3 ) $$ $$ x \equiv 3 (\text{mod } 5 ) $$ $$ x \equiv 2 (\text{mod } 7 ) $$ and the answer is $23$. In fact, this is the minimum possible solution. Starting from 23, you can get another possible answer by adding 105, i.e. $$ x = 23 + 105 * n $$ where $$ n \in {0, 1, 2, 3, \cdots} $$ Given a set of congruence equations, we are interested to find $a$ that produces the given remainders. $$ a \equiv a_1 (\text{mod } p_1 ) $$ $$ a \equiv a_2 (\text{mod } p_2 ) $$ $$ \cdots \\ $$ $$ a \equiv a_k (\text{mod } p_k ) $$ where every pair $p_i$ are pairwise coprime, $a_i$ are given constants.

## Problem: [Oversleeping](https://atcoder.jp/contests/abc193/tasks/abc193_e) In this problem, we are interested in finding the minimum non-negative integer t such that $$ X \le t \text{ mod } (2X + 2Y) \lt X + Y $$ $$ P \le t \text{ mod } (P + Q) \lt P + Q $$ We can solve this problem using Chinese Remainder Theorem. $$ t \equiv t_1 (\text{mod } 2X + 2Y ) $$ $$ t \equiv t_2 (\text{mod } P + Q ) $$ AtCoder has provided a crt library [here](https://github.com/atcoder/ac-library/blob/master/atcoder/math.hpp#L34), which makes the implementation relatively simple. ```cpp #include <atcoder/math> using namespace atcoder; const ll mx = numeric_limits<ll>::max(); void solve() { ll X, Y, P, Q; cin >> X >> Y >> P >> Q; ll ans = mx; for(ll t1 = X; t1 < X + Y; t1++) { for(ll t2 = P; t2 < P + Q; t2++) { auto [t, lcm] = crt( { t1, t2 }, // rem { 2 * X + 2 * Y, P + Q } // mod ); if(lcm == 0) { // no solution continue; } MIN(ans, t); } } if(ans == mx) OUT("infinity"); else OUT(ans); } ``` The full solution is available [here](https://github.com/wingkwong/competitive-programming/blob/master/atcoder/contests/abc193/E.cpp).