The CRT Solver: Chinese Remainder Theorem

In the ancient temple of Prime City, a stone tablet bears the Chinese Remainder Theorem ÔÇö a method discovered over 1500 years ago by Sun Tzu (not the military strategist). The theorem states: if n1, n2, ..., nk are pairwise coprime, then the system of congruences x Ôëí a1 (mod n1), x Ôëí a2 (mod n2), ..., x Ôëí ak (mod nk) has a unique solution modulo N = n1 * n2 * ... * nk. "The CRT is the backbone of modular computation," the temple keeper says. "Combine the congruences two at a time using the Extended Euclidean Algorithm, and you shall find the unique solution." Given k pairs (ai, ni) where the ni are pairwise coprime, find the smallest non-negative x satisfying all congruences x Ôëí ai (mod ni). Constraints: 1 <= k <= 10, 1 <= ai < ni <= 10^9, ni are pairwise coprime, product of all ni <= 10^18 Input: 2 2 3 3 5 2 7 Output: 23 Input: 1 5 11 Output: 5