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

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, which makes the implementation relatively simple.

#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.