∑MathIntermediate

Chinese Remainder Theorem

Key Points

•
The Chinese Remainder Theorem (CRT) reconstructs an integer from its remainders modulo pairwise coprime moduli and guarantees a unique answer modulo the product.
•
The constructive formula combines each remainder with a scaled inverse to cancel all other moduli.
•
When moduli are not coprime, a solution exists if and only if all remainders agree modulo the pairwise gcds.
•
Merging two congruences reduces the system step by step and works for both coprime and non-coprime cases.
•
In C++, use the Extended Euclidean Algorithm to compute modular inverses under non-prime moduli.
•
Beware of overflow: use __int128 for products and lcm, or use Garner’s algorithm to get the result modulo a final modulus without building the huge product.
•
Time complexity is roughly linear in the number of congruences, dominated by gcd/inverse computations.
•
CRT is vital in competitive programming for aligning cycles, reconstructing numbers from residues, and speeding up certain convolutions.

Prerequisites

→Modular arithmetic basics — Understand congruences, residues, and working modulo m.
→Greatest common divisor (gcd) — Used to check consistency and to compute lcm and inverses.
→Extended Euclidean Algorithm — Computes coefficients for Bézout identity and modular inverses.
→Modular inverse — Essential for the constructive formula and solving linear congruences.
→Integer overflow and data types — Choosing between 64-bit and __int128 to avoid overflow in products.
→Least common multiple (lcm) — Determines the modulus of the merged congruence in the general case.
→Algorithmic complexity — To estimate performance for k congruences and large moduli.

Detailed Explanation

Tap terms for definitions

01Overview

The Chinese Remainder Theorem (CRT) is a foundational result in number theory that lets you rebuild a whole number from its remainders with respect to several moduli. When the moduli are pairwise coprime (every pair shares gcd 1), CRT guarantees there is exactly one solution modulo the product of the moduli. In practice, this means if you know how a number behaves modulo, say, 3, 5, and 7, there is a unique integer between 0 and 104 (since 3×5×7=105) that fits all three residue conditions simultaneously. CRT is constructive: it not only guarantees a solution exists but also provides a way to compute it using modular inverses. When moduli are not coprime, CRT generalizes: a solution may or may not exist, and the condition for existence is that all the residues agree modulo the greatest common divisors of the corresponding moduli. In competitive programming, CRT is used to align independent cycles, stitch together partial computations, and handle modular arithmetic across multiple bases without collisions. Implementation typically relies on the Extended Euclidean Algorithm for computing inverses and for merging congruences while controlling overflow using 128-bit integers or specialized techniques like Garner’s algorithm.

02Intuition & Analogies

Imagine several clocks ticking at different speeds. One clock cycles every 3 hours, another every 5 hours, another every 7 hours. You’re told the current position on each clock but not the absolute time. CRT says that if these cycle lengths are pairwise coprime, then there is exactly one absolute time (up to the combined cycle length) that matches all clock readings simultaneously. This is like solving a puzzle where each clue (a remainder) narrows down the possibilities until only one consistent answer remains. Another analogy: think of barcodes made of several independent strips. Each strip carries partial information that by itself is ambiguous—but when you read all strips together, you can uniquely identify the object. Mathematically, each residue class “filters out” candidates that don’t match. With coprime moduli, the filters are independent in a very clean way, ensuring there’s a single candidate left modulo the product. The constructive formula works by building a linear combination of the residues, where each term is engineered to be 0 modulo all but its own modulus and equal to the target residue modulo its own. This engineering is done with modular inverses, acting like dials you turn so that the component aimed at modulus m_i vanishes for all other moduli. When moduli share factors (are not coprime), the filters are not independent; they may contradict each other unless the residues agree on the overlapping parts (the gcds).

03Formal Definition

Given integers

a_{1}

\dots

a_{k}

and moduli

m_{1}

\dots

m_{k}

with pairwise coprime moduli (

g cd

(

m_{i}

m_{j}

)=1 for i

\neq =

j), the system of congruences x

\equiv

a_{i}

(mod m_{i})

has a unique solution modulo M=

\prod_{i = 1}^{k}

m_{i}

. A constructive solution is given by x

\equiv

\sum_{i = 1}^{k}

a_{i}

M_{i}

y_{i}

(mod M)

, where

M_{i} = M / m_{i}

and

y_{i}

is the modular inverse of

M_{i}

modulo

m_{i}

, i.e.,

M_{i}

y_{i}

\equiv

(mod m_{i})

. For general moduli (not necessarily coprime), the system x

\equiv

a_{i}

(mod m_{i})

has a solution if and only if for all i,j,

a_{i}

\equiv

a_{j}

(mod g cd (m_{i}, m_{j}))

. When a solution exists, it is unique modulo

lcm

(

m_{1}

\dots

m_{k}

). Practically, one can merge congruences two at a time using the Extended Euclidean Algorithm: combining x

\equiv

(mod m)

and x

\equiv

(mod n)

yields a new congruence x

\equiv

(mod lcm (m, n))

or detects inconsistency when (b-a) is not divisible by

g cd

(m,n). This two-way merge generalizes to k congruences by iterating.

04When to Use

Use CRT when you need to reconstruct an integer from multiple modular views, especially when moduli are pairwise coprime. Typical cases include synchronizing repeating events (e.g., find the earliest time satisfying multiple periodic constraints), working with mixed bases, or combining results computed under smaller moduli to avoid overflow. In competitive programming, CRT appears in problems like aligning sequences with different cycles, solving Diophantine systems with modular constraints, or speeding up computations by performing them modulo several smaller coprime numbers and reassembling the final result. When the product of moduli is too large to store, or when you only need the answer modulo a final modulus P, Garner’s algorithm is preferred because it reconstructs the solution directly modulo P without ever forming the huge product. When moduli are not coprime, use the generalized merging approach that checks consistency via gcd conditions and produces a solution modulo the least common multiple. If your moduli are prime (or you operate under a prime modulus), modular inverses can also be computed via Fermat’s little theorem; otherwise, use the Extended Euclidean Algorithm.

⚠️Common Mistakes

Common pitfalls include: (1) Ignoring overflow. The product M=\prod m_{i} can exceed 64-bit limits easily. In C++, use int128 for intermediate products or avoid forming M by using Garner’s algorithm when you only need the result modulo another number. (2) Forgetting to normalize residues into the canonical range [0,m{i}). Negative residues are fine mathematically but can cause wrong code if not normalized consistently. (3) Computing modular inverses with Fermat’s little theorem when the modulus is not prime. For non-prime moduli, use the Extended Euclidean Algorithm and ensure gcd(a,m)=1; otherwise, no inverse exists. (4) Applying the coprime CRT formula to non-coprime moduli. Always check the consistency condition a{i} \equiv a_{j} \pmod{\gcd(m_{i},m_{j})} (or merge step-by-step with gcd checks). (5) Not reducing intermediate expressions modulo their moduli in iterative algorithms like Garner’s, leading to overflow or incorrect states. (6) Off-by-one in uniqueness: the solution is unique modulo the product (or lcm in the non-coprime case), not unique as an absolute integer. (7) Mixing 64-bit and 128-bit arithmetic in modular multiplication incorrectly; ensure all multiplicative paths that might overflow 64-bit are promoted to __int128 before multiplication.

Key Formulas

Product of moduli

M = i = 1 \prod k m_{i}

Explanation: When moduli are pairwise coprime, all solutions are unique modulo M, the product of the moduli. M is the size of the combined cycle.

Constructive CRT

x \equiv i = 1 \sum k a_{i} M_{i} y_{i} (mod M), M_{i} = \frac{M}{m _{i}}, M_{i} y_{i} \equiv 1 (mod m_{i})

Explanation: Each term equals $a_{i}$ modulo $m_{i}$ and 0 modulo all other $m_{j}$ . Summing them yields a solution modulo M. The $y_{i}$ are modular inverses.

Existence condition (non-coprime)

x \equiv a (mod m), x \equiv b (mod n) \Rightarrow solution exists iff a \equiv b (mod g cd (m, n))

Explanation: If the residues disagree on the common factors (the gcd), no integer can satisfy both congruences simultaneously.

Merging two congruences

x \equiv a + m \cdot t (mod lcm (m, n)), t \equiv (\frac{b - a}{g}) \cdot (\frac{m}{g})^{- 1} (mod \frac{n}{g}), g = g cd (m, n)

Explanation: This computes the merged residue and modulus by solving a linear congruence using a modular inverse modulo n/g. It generalizes step-by-step to many congruences.

Bézout identity

a x + b y = g cd (a, b)

Explanation: Extended Euclid finds integers x and y satisfying this. It is used to compute modular inverses and to merge congruences in CRT.

Euler inverse (theoretical)

a^{- 1} \equiv a^{φ (m) - 1} (mod m) when g cd (a, m) = 1

Explanation: A theoretical way to compute inverses modulo m using Euler's theorem. In practice, Extended Euclid is faster for arbitrary m.

Garner's algorithm recurrence

x_{j} = c_{j} + k_{j} t (Garner update), t \equiv (r_{i} - c_{i}) \cdot k_{i}^{- 1} (mod m_{i})

Explanation: Garner incrementally determines coefficients so that x matches residues $r_{i}$ modulo $m_{i}$ . It avoids building the large product and can target a final modulus.

Uniqueness modulus

Uniqueness: x is unique modulo M (coprime case), unique modulo lcm (m_{1}, \dots, m_{k}) (general case)

Explanation: Different integer representatives differ by a multiple of the combined modulus. This sets the period of all solutions.

Complexity Analysis

Let k be the number of congruences and let B be an upper bound on the bit-length of the moduli (so each modulus is O(2^B)). In the pairwise coprime constructive CRT, we compute the product M = ∏

m_{i}

(k−1 multiplications), each inverse

y_{i} = M_{i}^{- 1}

mod

m_{i}

via Extended Euclid, and the final linear combination. Using word operations (assuming 128-bit suffices) this runs in O(k) modular inversions and multiplications. More precisely, each Extended Euclidean Algorithm call takes O(log

m_{i}

) arithmetic steps, so the total time is O(∑ log

m_{i}

) ≈ O(k log max

m_{i}

). If we count bit operations, gcd/inverse is O(

B^{2}

) with schoolbook arithmetic, yielding O(k

B^{2}

) overall. The space usage is O(k) to store residues, moduli, and per-modulus contributions, plus O(1) extra for Extended Euclid. In the generalized CRT (non-coprime moduli), we iteratively merge two congruences at a time. Each merge requires one gcd/inverse on reduced moduli (m/g, n/g) and updates the combined residue and modulus (using lcm). This yields O(k) merges, each O(log max

m_{i}

), hence O(k log max

m_{i}

) time with O(1) extra space beyond input. Care must be taken for overflow: the lcm can be as large as the product; using 128-bit integers for intermediate arithmetic is recommended. Garner’s algorithm avoids constructing the big product M; it runs in O(

k^{2}

) modular operations because each of the k stages updates O(k) future coefficients. With Extended Euclid-based inverses, this is O(

k^{2}

log max

m_{i}

) time and O(k) space. Garner is advantageous when you only need the answer modulo a final modulus P and the product ∏

m_{i}

would overflow native types.

Code Examples

CRT for pairwise coprime moduli (constructive formula) with 128-bit safety

1 #include <bits/stdc++.h>
2 using namespace std;
3 
4 // Extended Euclidean Algorithm: returns gcd(a,b) and finds x,y such that ax + by = gcd(a,b)
5 __int128 extgcd(__int128 a, __int128 b, __int128 &x, __int128 &y) {
6     if (b == 0) { x = 1; y = 0; return a; }
7     __int128 x1, y1;
8     __int128 g = extgcd(b, a % b, x1, y1);
9     x = y1;
10     y = x1 - (a / b) * y1;
11     return g;
12 }
13 
14 // Modular inverse of a modulo m (assumes gcd(a,m)=1). Returns value in [0, m-1].
15 long long modInverse(long long a, long long m) {
16     __int128 x, y;
17     __int128 g = extgcd((__int128)a, (__int128)m, x, y);
18     if (g != 1) throw runtime_error("Inverse does not exist");
19     __int128 res = x % m; if (res < 0) res += m;
20     return (long long)res;
21 }
22 
23 // Convert __int128 to string for printing
24 string to_string_int128(__int128 v) {
25     if (v == 0) return "0";
26     bool neg = v < 0; if (neg) v = -v;
27     string s;
28     while (v > 0) { int d = (int)(v % 10); s.push_back('0' + d); v /= 10; }
29     if (neg) s.push_back('-');
30     reverse(s.begin(), s.end());
31     return s;
32 }
33 
34 // Solve x ≡ a[i] (mod m[i]) for pairwise coprime m[i]. Returns (x0, M) with x0 in [0, M-1].
35 pair<__int128, __int128> crt_coprime(const vector<long long>& a, const vector<long long>& m) {
36     int n = (int)a.size();
37     // 1) Compute M = product of moduli
38     __int128 M = 1;
39     for (int i = 0; i < n; ++i) M *= (__int128)m[i];
40 
41     // 2) Sum contributions a_i * M_i * inv(M_i mod m_i)
42     __int128 x = 0;
43     for (int i = 0; i < n; ++i) {
44         __int128 Mi = M / (__int128)m[i];
45         long long inv = modInverse((long long)(Mi % m[i]), m[i]);
46         __int128 term = ((__int128)a[i] * Mi) % M;
47         term = (term * inv) % M;
48         x = (x + term) % M;
49     }
50     if (x < 0) x += M;
51     return {x, M};
52 }
53 
54 int main() {
55     ios::sync_with_stdio(false);
56     cin.tie(nullptr);
57 
58     // Example: x ≡ 2 (mod 3), x ≡ 3 (mod 5), x ≡ 2 (mod 7)
59     vector<long long> a = {2, 3, 2};
60     vector<long long> m = {3, 5, 7};
61 
62     auto ans = crt_coprime(a, m);
63     cout << "x ≡ " << to_string_int128(ans.first) << " (mod " << to_string_int128(ans.second) << ")\n";
64     // Expected: x ≡ 23 (mod 105)
65 
66     return 0;
67 }
68

This program implements the constructive CRT for pairwise coprime moduli. It computes the product M, then for each i constructs the term a_i * M_i * inv(M_i mod m_i), sums them, and reduces modulo M. __int128 is used to avoid overflow in intermediate multiplications and to store M safely. The example produces x ≡ 23 (mod 105).

Time: O(k log max m_i)Space: O(k)

Generalized CRT (works for non-coprime moduli) via iterative merging

1 #include <bits/stdc++.h>
2 using namespace std;
3 
4 // Extended Euclidean Algorithm on 128-bit integers
5 __int128 extgcd(__int128 a, __int128 b, __int128 &x, __int128 &y) {
6     if (b == 0) { x = 1; y = 0; return a; }
7     __int128 x1, y1;
8     __int128 g = extgcd(b, a % b, x1, y1);
9     x = y1;
10     y = x1 - (a / b) * y1;
11     return g;
12 }
13 
14 // Normalize value into [0, m)
15 __int128 norm(__int128 v, __int128 m) { v %= m; if (v < 0) v += m; return v; }
16 
17 // Merge two congruences: x ≡ a1 (mod m1), x ≡ a2 (mod m2)
18 // Returns {a, m} meaning x ≡ a (mod m); if no solution, returns {0, -1}
19 pair<__int128, __int128> mergeCRT(__int128 a1, __int128 m1, __int128 a2, __int128 m2) {
20     // Handle trivial cases
21     if (m1 == -1 || m2 == -1) return {0, -1};
22     if (m1 == 1) return {norm(a2, m2), m2};
23     if (m2 == 1) return {norm(a1, m1), m1};
24 
25     a1 = norm(a1, m1); a2 = norm(a2, m2);
26 
27     __int128 x, y;
28     __int128 g = extgcd(m1, m2, x, y);
29     __int128 diff = a2 - a1;
30     if (diff % g != 0) return {0, (__int128)-1}; // inconsistent
31 
32     // Solve m1 * t ≡ (a2 - a1) (mod m2)
33     __int128 m1g = m1 / g, m2g = m2 / g;
34     // Inverse of m1/g modulo m2/g
35     __int128 x_inv = x % m2g; if (x_inv < 0) x_inv += m2g; // x is the inverse of m1/g modulo m2/g
36     __int128 t = ( (__int128)(diff / g) % m2g ) * x_inv % m2g;
37 
38     __int128 lcm = m1g * m2; // lcm(m1,m2) = m1 / g * m2 (128-bit safe)
39     __int128 a = a1 + m1 * t; a = norm(a, lcm);
40     return {a, lcm};
41 }
42 
43 string to_string_int128(__int128 v) {
44     if (v == 0) return "0";
45     bool neg = v < 0; if (neg) v = -v;
46     string s; while (v) { s.push_back('0' + (int)(v % 10)); v /= 10; }
47     if (neg) s.push_back('-'); reverse(s.begin(), s.end()); return s;
48 }
49 
50 int main(){
51     ios::sync_with_stdio(false);
52     cin.tie(nullptr);
53 
54     // Example 1: solvable non-coprime case
55     // x ≡ 2 (mod 6), x ≡ 8 (mod 9)
56     // gcd(6,9)=3, and 2 ≡ 8 (mod 3) holds, so a solution exists.
57     auto p1 = mergeCRT(2, 6, 8, 9);
58     cout << "Example 1: ";
59     if (p1.second == -1) cout << "No solution\n";
60     else cout << "x ≡ " << to_string_int128(p1.first) << " (mod " << to_string_int128(p1.second) << ")\n";
61 
62     // Example 2: inconsistent system
63     // x ≡ 1 (mod 4), x ≡ 2 (mod 6) -> gcd=2, but 1 ≡ 2 (mod 2) is false
64     auto p2 = mergeCRT(1, 4, 2, 6);
65     cout << "Example 2: ";
66     if (p2.second == -1) cout << "No solution\n";
67     else cout << "x ≡ " << to_string_int128(p2.first) << " (mod " << to_string_int128(p2.second) << ")\n";
68 
69     // Example 3: merge multiple constraints iteratively
70     vector<long long> a = {2, 3, 2};
71     vector<long long> m = {6, 5, 9}; // note: not all coprime
72     pair<__int128,__int128> cur = {0, 1};
73     for (int i = 0; i < (int)a.size(); ++i) {
74         cur = mergeCRT(cur.first, cur.second, a[i], m[i]);
75         if (cur.second == -1) break;
76     }
77     cout << "Example 3: ";
78     if (cur.second == -1) cout << "No solution\n";
79     else cout << "x ≡ " << to_string_int128(cur.first) << " (mod " << to_string_int128(cur.second) << ")\n";
80 
81     return 0;
82 }
83

This code merges congruences one pair at a time and works even when moduli share factors. It checks the consistency condition using gcd and computes the merged residue via a modular inverse on reduced moduli. The modulus grows to the lcm at each step. __int128 ensures safe arithmetic for large products.

Time: O(k log max m_i)Space: O(1) extra (O(k) for input)

Garner’s algorithm: reconstruct x modulo a final MOD without forming the big product

1 #include <bits/stdc++.h>
2 using namespace std;
3 
4 // Extended Euclid for inverses when moduli are not prime
5 long long extgcd_ll(long long a, long long b, long long &x, long long &y) {
6     if (b == 0) { x = (a >= 0 ? 1 : -1); y = 0; return llabs(a); }
7     long long x1, y1; long long g = extgcd_ll(b, a % b, x1, y1);
8     x = y1; y = x1 - (a / b) * y1; return g;
9 }
10 
11 long long modInverse_ll(long long a, long long m) {
12     long long x, y; long long g = extgcd_ll(a, m, x, y);
13     if (g != 1) throw runtime_error("inverse does not exist");
14     long long r = x % m; if (r < 0) r += m; return r;
15 }
16 
17 // Garner's algorithm assumes pairwise coprime moduli 'm'.
18 // Returns x modulo MOD (which must be coprime to all m[i]).
19 long long garner(const vector<long long>& r, const vector<long long>& m, long long MOD) {
20     int k = (int)m.size();
21     // Extended mod list includes the final MOD as the last modulus.
22     vector<long long> mods = m; mods.push_back(MOD);
23     vector<long long> coeff(k + 1, 1);   // k_j in literature
24     vector<long long> consts(k + 1, 0);  // c_j in literature
25 
26     for (int i = 0; i < k; ++i) {
27         // t = (r_i - consts[i]) * inv(coeff[i]) mod m_i
28         long long t = (r[i] - consts[i]) % m[i]; if (t < 0) t += m[i];
29         long long inv = modInverse_ll((coeff[i] % m[i] + m[i]) % m[i], m[i]);
30         t = (__int128)t * inv % m[i]; // promote to avoid overflow
31 
32         // Update future layers j > i
33         for (int j = i + 1; j <= k; ++j) {
34             consts[j] = (consts[j] + (__int128)coeff[j] * t) % mods[j]; if (consts[j] < 0) consts[j] += mods[j];
35             coeff[j] = (__int128)coeff[j] * m[i] % mods[j]; if (coeff[j] < 0) coeff[j] += mods[j];
36         }
37     }
38     return consts[k]; // This is x modulo MOD
39 }
40 
41 int main(){
42     ios::sync_with_stdio(false);
43     cin.tie(nullptr);
44 
45     // Example: reconstruct x from residues modulo pairwise coprime moduli, but only need x mod 1e9+7
46     vector<long long> r = {2, 3, 2};
47     vector<long long> m = {3, 5, 7}; // pairwise coprime
48     const long long MOD = 1000000007LL;
49 
50     long long x_mod = garner(r, m, MOD);
51     cout << "x mod 1e9+7 = " << x_mod << "\n"; // Should equal 23
52 
53     return 0;
54 }
55

Garner’s algorithm computes the CRT solution layer by layer without forming the giant product M. By appending the target MOD as the last modulus, the algorithm returns the solution modulo MOD. It requires pairwise coprime moduli and uses modular inverses under each m[i]. This is ideal when ∏m[i] does not fit in 64-bit or when only x mod MOD is needed.

Time: O(k^2 log max m_i)Space: O(k)

1	#include <bits/stdc++.h>
2	using namespace std;
3
4	// Extended Euclidean Algorithm: returns gcd(a,b) and finds x,y such that ax + by = gcd(a,b)
5	__int128 extgcd(__int128 a, __int128 b, __int128 &x, __int128 &y) {
6	if (b == 0) { x = 1; y = 0; return a; }
7	__int128 x1, y1;
8	__int128 g = extgcd(b, a % b, x1, y1);
9	x = y1;
10	y = x1 - (a / b) * y1;
11	return g;
12	}
13
14	// Modular inverse of a modulo m (assumes gcd(a,m)=1). Returns value in [0, m-1].
15	long long modInverse(long long a, long long m) {
16	__int128 x, y;
17	__int128 g = extgcd((__int128)a, (__int128)m, x, y);
18	if (g != 1) throw runtime_error("Inverse does not exist");
19	__int128 res = x % m; if (res < 0) res += m;
20	return (long long)res;
21	}
22
23	// Convert __int128 to string for printing
24	string to_string_int128(__int128 v) {
25	if (v == 0) return "0";
26	bool neg = v < 0; if (neg) v = -v;
27	string s;
28	while (v > 0) { int d = (int)(v % 10); s.push_back('0' + d); v /= 10; }
29	if (neg) s.push_back('-');
30	reverse(s.begin(), s.end());
31	return s;
32	}
33
34	// Solve x ≡ a[i] (mod m[i]) for pairwise coprime m[i]. Returns (x0, M) with x0 in [0, M-1].
35	pair<__int128, __int128> crt_coprime(const vector<long long>& a, const vector<long long>& m) {
36	int n = (int)a.size();
37	// 1) Compute M = product of moduli
38	__int128 M = 1;
39	for (int i = 0; i < n; ++i) M *= (__int128)m[i];
40
41	// 2) Sum contributions a_i * M_i * inv(M_i mod m_i)
42	__int128 x = 0;
43	for (int i = 0; i < n; ++i) {
44	__int128 Mi = M / (__int128)m[i];
45	long long inv = modInverse((long long)(Mi % m[i]), m[i]);
46	__int128 term = ((__int128)a[i] * Mi) % M;
47	term = (term * inv) % M;
48	x = (x + term) % M;
49	}
50	if (x < 0) x += M;
51	return {x, M};
52	}
53
54	int main() {
55	ios::sync_with_stdio(false);
56	cin.tie(nullptr);
57
58	// Example: x ≡ 2 (mod 3), x ≡ 3 (mod 5), x ≡ 2 (mod 7)
59	vector<long long> a = {2, 3, 2};
60	vector<long long> m = {3, 5, 7};
61
62	auto ans = crt_coprime(a, m);
63	cout << "x ≡ " << to_string_int128(ans.first) << " (mod " << to_string_int128(ans.second) << ")\n";
64	// Expected: x ≡ 23 (mod 105)
65
66	return 0;
67	}
68

1	#include <bits/stdc++.h>
2	using namespace std;
3
4	// Extended Euclidean Algorithm on 128-bit integers
5	__int128 extgcd(__int128 a, __int128 b, __int128 &x, __int128 &y) {
6	if (b == 0) { x = 1; y = 0; return a; }
7	__int128 x1, y1;
8	__int128 g = extgcd(b, a % b, x1, y1);
9	x = y1;
10	y = x1 - (a / b) * y1;
11	return g;
12	}
13
14	// Normalize value into [0, m)
15	__int128 norm(__int128 v, __int128 m) { v %= m; if (v < 0) v += m; return v; }
16
17	// Merge two congruences: x ≡ a1 (mod m1), x ≡ a2 (mod m2)
18	// Returns {a, m} meaning x ≡ a (mod m); if no solution, returns {0, -1}
19	pair<__int128, __int128> mergeCRT(__int128 a1, __int128 m1, __int128 a2, __int128 m2) {
20	// Handle trivial cases
21	if (m1 == -1 \|\| m2 == -1) return {0, -1};
22	if (m1 == 1) return {norm(a2, m2), m2};
23	if (m2 == 1) return {norm(a1, m1), m1};
24
25	a1 = norm(a1, m1); a2 = norm(a2, m2);
26
27	__int128 x, y;
28	__int128 g = extgcd(m1, m2, x, y);
29	__int128 diff = a2 - a1;
30	if (diff % g != 0) return {0, (__int128)-1}; // inconsistent
31
32	// Solve m1 * t ≡ (a2 - a1) (mod m2)
33	__int128 m1g = m1 / g, m2g = m2 / g;
34	// Inverse of m1/g modulo m2/g
35	__int128 x_inv = x % m2g; if (x_inv < 0) x_inv += m2g; // x is the inverse of m1/g modulo m2/g
36	__int128 t = ( (__int128)(diff / g) % m2g ) * x_inv % m2g;
37
38	__int128 lcm = m1g * m2; // lcm(m1,m2) = m1 / g * m2 (128-bit safe)
39	__int128 a = a1 + m1 * t; a = norm(a, lcm);
40	return {a, lcm};
41	}
42
43	string to_string_int128(__int128 v) {
44	if (v == 0) return "0";
45	bool neg = v < 0; if (neg) v = -v;
46	string s; while (v) { s.push_back('0' + (int)(v % 10)); v /= 10; }
47	if (neg) s.push_back('-'); reverse(s.begin(), s.end()); return s;
48	}
49
50	int main(){
51	ios::sync_with_stdio(false);
52	cin.tie(nullptr);
53
54	// Example 1: solvable non-coprime case
55	// x ≡ 2 (mod 6), x ≡ 8 (mod 9)
56	// gcd(6,9)=3, and 2 ≡ 8 (mod 3) holds, so a solution exists.
57	auto p1 = mergeCRT(2, 6, 8, 9);
58	cout << "Example 1: ";
59	if (p1.second == -1) cout << "No solution\n";
60	else cout << "x ≡ " << to_string_int128(p1.first) << " (mod " << to_string_int128(p1.second) << ")\n";
61
62	// Example 2: inconsistent system
63	// x ≡ 1 (mod 4), x ≡ 2 (mod 6) -> gcd=2, but 1 ≡ 2 (mod 2) is false
64	auto p2 = mergeCRT(1, 4, 2, 6);
65	cout << "Example 2: ";
66	if (p2.second == -1) cout << "No solution\n";
67	else cout << "x ≡ " << to_string_int128(p2.first) << " (mod " << to_string_int128(p2.second) << ")\n";
68
69	// Example 3: merge multiple constraints iteratively
70	vector<long long> a = {2, 3, 2};
71	vector<long long> m = {6, 5, 9}; // note: not all coprime
72	pair<__int128,__int128> cur = {0, 1};
73	for (int i = 0; i < (int)a.size(); ++i) {
74	cur = mergeCRT(cur.first, cur.second, a[i], m[i]);
75	if (cur.second == -1) break;
76	}
77	cout << "Example 3: ";
78	if (cur.second == -1) cout << "No solution\n";
79	else cout << "x ≡ " << to_string_int128(cur.first) << " (mod " << to_string_int128(cur.second) << ")\n";
80
81	return 0;
82	}
83

1	#include <bits/stdc++.h>
2	using namespace std;
3
4	// Extended Euclid for inverses when moduli are not prime
5	long long extgcd_ll(long long a, long long b, long long &x, long long &y) {
6	if (b == 0) { x = (a >= 0 ? 1 : -1); y = 0; return llabs(a); }
7	long long x1, y1; long long g = extgcd_ll(b, a % b, x1, y1);
8	x = y1; y = x1 - (a / b) * y1; return g;
9	}
10
11	long long modInverse_ll(long long a, long long m) {
12	long long x, y; long long g = extgcd_ll(a, m, x, y);
13	if (g != 1) throw runtime_error("inverse does not exist");
14	long long r = x % m; if (r < 0) r += m; return r;
15	}
16
17	// Garner's algorithm assumes pairwise coprime moduli 'm'.
18	// Returns x modulo MOD (which must be coprime to all m[i]).
19	long long garner(const vector<long long>& r, const vector<long long>& m, long long MOD) {
20	int k = (int)m.size();
21	// Extended mod list includes the final MOD as the last modulus.
22	vector<long long> mods = m; mods.push_back(MOD);
23	vector<long long> coeff(k + 1, 1); // k_j in literature
24	vector<long long> consts(k + 1, 0); // c_j in literature
25
26	for (int i = 0; i < k; ++i) {
27	// t = (r_i - consts[i]) * inv(coeff[i]) mod m_i
28	long long t = (r[i] - consts[i]) % m[i]; if (t < 0) t += m[i];
29	long long inv = modInverse_ll((coeff[i] % m[i] + m[i]) % m[i], m[i]);
30	t = (__int128)t * inv % m[i]; // promote to avoid overflow
31
32	// Update future layers j > i
33	for (int j = i + 1; j <= k; ++j) {
34	consts[j] = (consts[j] + (__int128)coeff[j] * t) % mods[j]; if (consts[j] < 0) consts[j] += mods[j];
35	coeff[j] = (__int128)coeff[j] * m[i] % mods[j]; if (coeff[j] < 0) coeff[j] += mods[j];
36	}
37	}
38	return consts[k]; // This is x modulo MOD
39	}
40
41	int main(){
42	ios::sync_with_stdio(false);
43	cin.tie(nullptr);
44
45	// Example: reconstruct x from residues modulo pairwise coprime moduli, but only need x mod 1e9+7
46	vector<long long> r = {2, 3, 2};
47	vector<long long> m = {3, 5, 7}; // pairwise coprime
48	const long long MOD = 1000000007LL;
49
50	long long x_mod = garner(r, m, MOD);
51	cout << "x mod 1e9+7 = " << x_mod << "\n"; // Should equal 23
52
53	return 0;
54	}
55