Chinese Remainder Theorem

You are given k congruences of the form x = a_i (mod m_i) for i = 1..k, where the moduli m_1, ..., m_k are pairwise coprime (gcd(m_i, m_j) = 1 for every i != j). Find the smallest non-negative integer x that satisfies all k congruences simultaneously. Since the moduli are pairwise coprime, the Chinese Remainder Theorem guarantees a unique solution modulo M, the product of all the moduli.

Input: The first line contains a single integer k. Each of the next k lines contains two space-separated integers a_i and m_i, describing one congruence x = a_i (mod m_i). Output: Print a single integer: the smallest non-negative x with 0 <= x < M (M being the product of all moduli) that satisfies every congruence.

1 <= k <= 10, 0 <= a_i < m_i <= 10^5, and the m_i are pairwise coprime

The need for BigInteger arithmetic here (rather than a standard 64-bit type) is a direct consequence of M being a PRODUCT of up to 10 moduli, each up to 10^5 - a good reminder to always check whether a computation's intermediate values could exceed fixed-width integer limits.

Find a single number that simultaneously satisfies several 'remainder when divided by' conditions, using coprime divisors. Brute force: Try every non-negative integer starting from 0 upward, checking if it satisfies ALL the congruences directly - this works for small moduli but can take up to M steps, which becomes impractical as the moduli grow (M can reach roughly 10^50 here). Optimised: The Chinese Remainder Theorem's CONSTRUCTIVE formula directly builds the unique solution using modular inverses (computed via the Extended Euclidean Algorithm), avoiding any brute-force search entirely - each congruence contributes one term to a sum that, taken modulo M, satisfies every congruence simultaneously by construction.

1. Compute the total modulus M as the PRODUCT of all the given moduli, and for each congruence i, compute M_i = M / m_i. 2. Since M_i and m_i are guaranteed coprime, M_i has a modular inverse modulo m_i (found via the Extended Euclidean Algorithm) - accumulate a_i * M_i * inverse(M_i) into a running sum for EVERY congruence. 3. The final answer is that running sum taken modulo M, using arbitrary-precision arithmetic (like BigInteger) since M can become astronomically large.

Time: O(k * log(max modulus)), where k is the number of congruences - each requires one Extended Euclidean computation for its modular inverse. Space: O(k) for the intermediate values, though the ARITHMETIC itself requires arbitrary-precision (BigInteger) support since M can be astronomically large.

k=1 means the answer is simply a_1 itself, already within [0, m_1). The moduli are guaranteed pairwise coprime, so a solution always exists and is unique modulo M; you do not need to detect an unsolvable system. Because M can be far larger than any fixed-width integer type can hold, computing with plain long arithmetic would silently overflow.

Be ready to explain why the moduli must be PAIRWISE COPRIME for this exact formula to work - the theorem's guarantee of a unique solution modulo M relies specifically on this coprimality condition.