∑MathIntermediate

Extended Euclidean Algorithm

Key Points

•
The Extended Euclidean Algorithm finds integers x and y such that ax + by = gcd(a, b) while also computing gcd(a, b).
•
It extends the classic Euclidean Algorithm by keeping track of how the gcd is built from a and b at each step.
•
The algorithm runs in O(log min(|a|, |b|)) time, making it extremely fast even for large integers.
•
A key application is computing modular inverses, which exist exactly when gcd(a, m) = 1.
•
It also solves linear Diophantine equations ax + by = c; a solution exists iff gcd(a, b) divides c.
•
Used inside the Chinese Remainder Theorem to merge congruences and find a unique solution modulo the lcm of moduli (when consistent).
•
Implementation pitfalls include negative numbers, division rounding, and modular normalization.
•
Both recursive and iterative C++ implementations are short, safe, and standard in competitive programming.

Prerequisites

→Greatest Common Divisor and Euclidean Algorithm — Extended Euclid builds on the remainder sequence from the classic Euclidean Algorithm.
→Integer Division and Modulo — Understanding a = bq + r with 0 ≤ r < |b| is essential for the update steps and correctness.
→Modular Arithmetic Basics — Applications like modular inverses and CRT rely on congruences and normalization.
→Recursion and Iteration — Both recursive and iterative forms of EEA are standard; understanding either helps with implementation.
→Overflow and Fixed-Width Integers — CRT merging can overflow 64-bit; knowledge of __int128 is practical in C++.

Detailed Explanation

Tap terms for definitions

01Overview

Hook: Imagine splitting a large pile of bricks into equal stacks with two different shovel sizes a and b. The largest equal stack size you can guarantee is the greatest common divisor gcd(a, b). But if you also want to know how to recombine some number of size-a shovelfuls and size-b shovelfuls to make exactly that gcd, you need more than just the gcd—you need the recipe. Concept: The Extended Euclidean Algorithm (EEA) not only computes gcd(a, b) but also provides integers x and y (called Bézout coefficients) such that ax + by = gcd(a, b). This identity is powerful because it connects the gcd with linear combinations of the original numbers. Example: For a = 30 and b = 18, gcd(30, 18) = 6. EEA will produce x = -1 and y = 2, since 30(−1) + 18(2) = −30 + 36 = 6. These coefficients come for free while running Euclid’s classic remainder steps. The extended version simply records how each remainder is made from a and b, back-substituting to reveal x and y. With these coefficients we can, for example, compute modular inverses and solve equations like 30x + 18y = c or merge congruences in CRT. Because it takes only logarithmic time, EEA is a staple for programming contests and cryptography.

02Intuition & Analogies

Think of the Euclidean Algorithm as repeatedly exchanging change between two coin denominations a and b to reduce the remainder until nothing is left. At each step, you trade as many of the larger coin as possible for the smaller one, and the leftover remainder becomes the new target. Eventually, the remainder is zero, and the last non-zero remainder is gcd(a, b). The extended version asks: if the final gcd is made from some number of these exchanges, can we write that gcd exactly as ax + by? Intuition for back-substitution: Every time you write r = a − q b during division, that equation tells you how r is built from a and b. Later, when you express the gcd as a combination of b and r, you can substitute r = a − q b to rewrite it as a combination of a and b. Doing this repeatedly unwinds the algorithm and yields the coefficients x and y. A cooking analogy: Suppose a special sauce (the gcd) is made by mixing base sauces A and B in steps. You first create some intermediate mixtures (the remainders). Each intermediate recipe shows exact proportions of A and B. By substituting these recipes backward, you end up with a single recipe expressing the final sauce as a direct mix of A and B—that’s ax + by = gcd(a, b). Example progression for (a, b) = (99, 78): 99 = 1·78 + 21, 78 = 3·21 + 15, 21 = 1·15 + 6, 15 = 2·6 + 3, 6 = 2·3 + 0. Now back-substitute to write 3 as 99x + 78y. That chain of substitutions is exactly what EEA automates.

03Formal Definition

Given integers a and b (not both zero), the Extended Euclidean Algorithm computes integers x and y satisfying Bézout’s identity: a x + b y =

g cd

(a, b). The algorithm is based on the division algorithm: for integers a and b

\neq =

0, there exist unique integers q and r with 0

\leq

r <

∣ b ∣

such that

a = b

q + r. The classical Euclidean Algorithm repeatedly replaces (a, b) by (b, r) until

r = 0

, at which point

∣ b ∣

is the gcd. The extended version augments this process: at each step, in addition to computing q and r, it maintains representations of the current a and b as linear combinations of the original inputs. Concretely, if at some step we have

g cd

(b, r) = b x' + r y' and

r = a - q

b, then

g cd

(a, b) = a y' + b (x' - q y'). This recurrence yields updated coefficients (x, y) for the pair (a, b). When the algorithm terminates with

b = 0

, we take x =

sgn

(a) and

y = 0

, and the gcd is

∣ a ∣

, ensuring a x + b y =

g cd

(a, b). The algorithm runs in O(

lo g

min

(

∣ a ∣

∣ b ∣

)) arithmetic steps and produces one valid pair (x, y); many other pairs exist, differing by integer multiples of (b/g, -a/g) where g =

g cd

(a, b).

04When to Use

Use the Extended Euclidean Algorithm whenever you need both gcd(a, b) and explicit coefficients expressing that gcd as ax + by. Key scenarios: 1) Modular inverse: To compute a^{-1} \bmod m, use EEA to find x, y with ax + my = 1 (possible iff gcd(a, m) = 1). Then x \bmod m is the modular inverse. 2) Linear Diophantine equations: To solve ax + by = c over integers, compute g = gcd(a, b). A solution exists iff g | c. If (x0, y0) satisfies ax0 + by0 = g, then (x, y) = (x0·(c/g), y0·(c/g)) is a particular solution, and all solutions are given by x = x_p + (b/g)t, y = y_p − (a/g)t for integer t. 3) Chinese Remainder Theorem (CRT): To merge congruences x \equiv r_1 (\bmod m_1) and x \equiv r_2 (\bmod m_2), use EEA to solve for a bridging variable even when moduli are not coprime; a consistent solution exists iff r_1 \equiv r_2 (\bmod \gcd(m_1, m_2)). 4) Rational reconstruction and fraction simplification: EEA underlies methods to express ratios as simplified fractions and to invert large numbers modulo primes in cryptographic systems. In programming contests, employ EEA whenever modular inverses or CRT merging appear, especially under constraints with large 64-bit numbers.

⚠️Common Mistakes

• Ignoring signs and division rounding: In C++, integer division truncates toward zero, not floor, which can break formulas with negative numbers. A robust fix is to run EEA on |a| and |b|, then reapply signs at the end. • Forgetting to normalize modulo: After computing an inverse x, always bring it into [0, m-1] using x = (x % m + m) % m; otherwise comparisons and further operations can misbehave. • Not checking gcd conditions: The inverse a^{-1} \bmod m exists iff gcd(a, m) = 1. For ax + by = c, solutions exist iff gcd(a, b) | c. Skipping these checks leads to wrong answers. • Overflow with 64-bit arithmetic: When combining congruences in CRT, intermediate products like m1 * t can exceed 64-bit. Use __int128 for intermediate multiplications and reduce modulo the new lcm early. • Returning negative gcd: Ensure the function returns a non-negative gcd and that the identity a x + b y = gcd(a, b) holds exactly. • Mixing recursive and iterative coefficient updates: If you hand-derive updates, a single swapped variable or sign error yields incorrect coefficients; prefer tested patterns. • Forgetting general solution parameterization: After finding one solution to ax + by = c, remember that all solutions involve a free integer parameter t with step sizes b/g and a/g. • Misusing CRT with inconsistent congruences: If r1 \not\equiv r2 (mod g), there is no solution; code must detect and report inconsistency.

Key Formulas

Bézout's Identity

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

Explanation: There exist integers x and y such that this equality holds. The Extended Euclidean Algorithm computes one such pair (x, y) together with the gcd.

Division Algorithm

a = b q + r, 0 \leq r < ∣ b ∣

Explanation: At each step of Euclid’s algorithm we divide a by b to get quotient q and remainder r. This drives the algorithm towards a remainder of zero.

Inductive Step (Premise)

g cd (b, a mod b) = b x^{'} + (a mod b) y^{'}

Explanation: Assume we know coefficients x', y' for the next pair (b, a mod b). We will transform them into coefficients for (a, b).

Coefficient Update

g cd (a, b) = a y^{'} + b (x^{'} - ⌊ \frac{a}{b} ⌋ y^{'})

Explanation: Because a $mod$ $b = a$ − $⌊$ a/b $⌋$ b, substituting into the premise yields new coefficients for (a, b).

Time Complexity

T (n) = O (lo g n)

Explanation: The number of division steps in Euclid’s algorithm grows logarithmically with the size of the inputs. Each step performs constant-time arithmetic on fixed-width integers.

Fibonacci Step Bound

k \leq lo g_{φ} (n 5)

Explanation: If k steps occur, the smaller input is at least the (k+1)-th Fibonacci number. Thus k grows like O(log n), with base related to the golden ratio $φ$ .

Inverse Existence

a x \equiv 1 (mod m) ⟺ g cd (a, m) = 1

Explanation: A modular inverse exists exactly when a and m are coprime. When it exists, the EEA gives x, and x mod m is the inverse.

Diophantine Solvability

a x + b y = c has a solution ⟺ g cd (a, b) ∣ c

Explanation: The equation has integer solutions only when c is a multiple of the gcd. Then we scale Bézout coefficients by c/g.

General Solution (Diophantine)

x = x_{0} + \frac{b}{g} t, y = y_{0} - \frac{a}{g} t, t \in Z

Explanation: If (x0, y0) is one solution of ax + by = c with g = gcd(a, b), then all solutions are given by shifting along these step sizes.

CRT Merge (Two Moduli)

x \equiv r_{1} (mod m_{1}), x \equiv r_{2} (mod m_{2}) \Rightarrow x \equiv r_{1} + m_{1} \cdot t_{0} (mod lcm (m_{1}, m_{2}))

Explanation: t0 is found using EEA, provided r1 $\equiv$ r2 (mod gcd(m1, m2)). The merged modulus is lcm(m1, m2).

Complexity Analysis

Each iteration of the Extended Euclidean Algorithm performs one division with remainder, some multiplications/additions for coefficient updates, and a swap. The sequence of remainders strictly decreases and is bounded below by zero, so termination is guaranteed. The worst case for the number of iterations occurs when inputs are consecutive Fibonacci numbers; in that case, the number of steps k grows proportionally to log n. Formally, if the smaller input is at most n, then

k \leq l o g_{φ} (n \sqrt5

) where φ is the golden ratio. Thus the time complexity is O(log min(

∣ a ∣

∣ b ∣

)). On modern machines with fixed-width 64-bit integers, each arithmetic operation is O(1), making the overall procedure extremely fast in practice. Space complexity depends on the implementation: the recursive variant uses O(log n) stack frames because each remainder step recurses once; the iterative variant uses O(1) extra space, holding a constant number of integers for coefficients and remainders. When used within higher-level tasks such as modular inversion or CRT merging of k congruences, the overall complexity scales to O(k log M), where M is a typical modulus size, plus the cost of modular multiplications. Care must be taken to avoid 64-bit overflow in intermediate products during CRT; using 128-bit intermediates (__int128 in C++) keeps the algorithm’s space overhead constant while preserving correctness.

Code Examples

Recursive Extended Euclidean Algorithm with Sign-Safe Wrapper

1 #include <bits/stdc++.h>
2 using namespace std;
3 using ll = long long;
4 
5 // Internal helper: extended gcd on non-negative inputs only.
6 // Computes: returns g = gcd(a, b) >= 0 and finds x, y with a*x + b*y = g.
7 static ll exgcd_nonneg(ll a, ll b, ll &x, ll &y) {
8     if (b == 0) { x = 1; y = 0; return a; }
9     ll x1, y1;
10     ll g = exgcd_nonneg(b, a % b, x1, y1);
11     // From: g = b*x1 + (a%b)*y1 = b*x1 + (a - (a/b)*b)*y1 = a*y1 + b*(x1 - (a/b)*y1)
12     x = y1;
13     y = x1 - (a / b) * y1; // safe: a,b >= 0 so C++ truncation equals floor
14     return g;
15 }
16 
17 // Public wrapper: works for any signs of a, b. Ensures g >= 0 and a*x + b*y = g.
18 ll extended_gcd(ll a, ll b, ll &x, ll &y) {
19     ll A = llabs(a), B = llabs(b);
20     if (A == 0 && B == 0) { x = 0; y = 0; return 0; } // convention
21     ll x0, y0;
22     ll g = exgcd_nonneg(A, B, x0, y0);
23     // Reapply signs so that a*x + b*y = g
24     x = (a >= 0 ? x0 : -x0);
25     y = (b >= 0 ? y0 : -y0);
26     return g;
27 }
28 
29 int main() {
30     // Example 1: basic test
31     ll a = 30, b = 18; ll x, y; ll g = extended_gcd(a, b, x, y);
32     cout << "gcd(" << a << ", " << b << ") = " << g << "\n";
33     cout << "Coefficients: x = " << x << ", y = " << y << "\n";
34     cout << "Check: a*x + b*y = " << a*x + b*y << "\n\n";
35 
36     // Example 2: with negatives
37     a = -91; b = 35; g = extended_gcd(a, b, x, y);
38     cout << "gcd(" << a << ", " << b << ") = " << g << "\n";
39     cout << "Coefficients: x = " << x << ", y = " << y << "\n";
40     cout << "Check: a*x + b*y = " << a*x + b*y << "\n";
41     return 0;
42 }
43

We implement the classic recursive EEA on non-negative inputs to avoid issues with floor vs truncation. A thin wrapper reapplies the original signs to produce x and y for the given a and b. The program tests both positive and negative inputs and verifies ax + by equals gcd(a, b).

Time: O(log min(|a|, |b|))Space: O(log min(|a|, |b|)) due to recursion

Iterative Extended Euclidean Algorithm (O(1) extra space)

1 #include <bits/stdc++.h>
2 using namespace std; using ll = long long; using i128 = __int128_t;
3 
4 // Iterative extended Euclid working with non-negative a,b then reapply signs.
5 ll extended_gcd_iter(ll a, ll b, ll &x, ll &y) {
6     ll A = llabs(a), B = llabs(b);
7     ll old_r = A, r = B;
8     ll old_s = 1, s = 0; // coefficients for A
9     ll old_t = 0, t = 1; // coefficients for B
10     while (r != 0) {
11         ll q = old_r / r; // A,B >= 0 so this is floor
12         ll tmp;
13         tmp = old_r - q * r; old_r = r; r = tmp;
14         tmp = old_s - q * s; old_s = s; s = tmp;
15         tmp = old_t - q * t; old_t = t; t = tmp;
16     }
17     // old_r is gcd(A, B), and A*old_s + B*old_t = old_r
18     x = (a >= 0 ? old_s : -old_s);
19     y = (b >= 0 ? old_t : -old_t);
20     return old_r;
21 }
22 
23 int main(){
24     ll a = 99, b = 78; ll x, y; ll g = extended_gcd_iter(a, b, x, y);
25     cout << "gcd("<<a<<","<<b<<")="<<g<<" with x="<<x<<", y="<<y<<"\n";
26     cout << "Check: " << a*x + b*y << "\n";
27     // Compare to std::gcd
28     cout << "std::gcd gives: " << std::gcd(llabs(a), llabs(b)) << "\n";
29     return 0;
30 }
31

This is the tabular (Old/New) iterative form of EEA. It keeps track of two rows of coefficients and reassigns them each division step. It uses constant extra space and avoids recursion, which is often preferred in contest code.

Time: O(log min(|a|, |b|))Space: O(1)

Modular Inverse via Extended GCD with Safe Normalization

1 #include <bits/stdc++.h>
2 using namespace std; using ll = long long; using i128 = __int128_t;
3 
4 ll extended_gcd(ll a, ll b, ll &x, ll &y) {
5     ll A = llabs(a), B = llabs(b);
6     if (A == 0 && B == 0) { x = 0; y = 0; return 0; }
7     if (B == 0) { x = (a >= 0 ? 1 : -1); y = 0; return A; }
8     ll x1, y1; ll g = extended_gcd(b, a % b, x1, y1);
9     x = y1;
10     y = x1 - (a / b) * y1;
11     return (g < 0 ? -g : g);
12 }
13 
14 // Normalize to [0, m-1]
15 ll norm_mod(ll x, ll m) { x %= m; if (x < 0) x += m; return x; }
16 
17 // Returns pair (exists, inverse). If no inverse, exists=false and inverse=0.
18 pair<bool,ll> mod_inverse(ll a, ll m) {
19     if (m <= 0) return {false, 0};
20     ll x, y; ll g = extended_gcd(a, m, x, y);
21     if (g != 1 && g != -1) return {false, 0}; // inverse exists iff gcd(a,m)=1
22     ll inv = norm_mod(x, m);
23     return {true, inv};
24 }
25 
26 int main(){
27     vector<pair<ll,ll>> tests = {{3,11},{10,17},{12,18},{-7,13}};
28     for (auto [a,m] : tests) {
29         auto [ok, inv] = mod_inverse(a, m);
30         cout << "a="<<a<<", m="<<m<<" -> ";
31         if (!ok) cout << "no inverse\n";
32         else {
33             cout << "inverse="<<inv<<" (check: "<< (( (__int128)a*inv) % m + m) % m << ")\n";
34         }
35     }
36     return 0;
37 }
38

We compute the modular inverse of a modulo m using EEA. The inverse exists exactly when gcd(a, m) = 1. The result is normalized to [0, m−1]. The demo includes a failing case (12 mod 18 has no inverse) and a negative a case.

Time: O(log m)Space: O(1) expected; recursion stack may add O(log m) if deeply nested

Generalized Chinese Remainder Theorem (merge many congruences)

1 #include <bits/stdc++.h>
2 using namespace std; using ll = long long; using i128 = __int128_t;
3 
4 // Extended GCD on non-negative a,b; returns g and finds x,y with a*x + b*y = g.
5 static ll exgcd_nonneg(ll a, ll b, ll &x, ll &y){ if(b==0){x=1;y=0;return a;} ll x1,y1; ll g=exgcd_nonneg(b,a%b,x1,y1); x=y1; y=x1-(a/b)*y1; return g; }
6 
7 // Solve m1 * p + m2 * q = g and also return g = gcd(m1,m2), with correct signs for m1,m2
8 static ll extended_gcd_signed(ll m1, ll m2, ll &p, ll &q){ ll A=llabs(m1), B=llabs(m2); ll x0,y0; ll g=exgcd_nonneg(A,B,x0,y0); p=(m1>=0?x0:-x0); q=(m2>=0?y0:-y0); return g; }
9 
10 static ll norm_mod(ll x, ll m){ x%=m; if(x<0) x+=m; return x; }
11 
12 // Safe multiply (a*b) mod m using 128-bit to avoid overflow
13 static ll mul_mod(ll a, ll b, ll m){ return (ll)((i128)a * (i128)b % (i128)m); }
14 
15 // Merge two congruences: x ≡ r1 (mod m1), x ≡ r2 (mod m2)
16 // Returns (r, l) where solution set is x ≡ r (mod l). If no solution, l = -1.
17 static pair<ll,ll> crt_merge(ll r1, ll m1, ll r2, ll m2){
18     if (m1 == -1 || m2 == -1) return {0, -1};
19     if (m1 == 0) return {norm_mod(r2, m2), m2};
20     if (m2 == 0) return {norm_mod(r1, m1), m1};
21     r1 = norm_mod(r1, m1); r2 = norm_mod(r2, m2);
22     ll p, q; ll g = extended_gcd_signed(m1, m2, p, q); // m1*p + m2*q = g
23     ll diff = r2 - r1;
24     if (diff % g != 0) return {0, -1}; // inconsistent
25     ll m2_g = m2 / g;
26     // t0 = (diff/g) * inv(m1/g mod m2/g). Here p is inverse of m1/g modulo m2/g.
27     ll t0 = mul_mod(diff / g, p, m2_g);
28     // New solution and modulus
29     i128 lcm = (i128)m1 / g * (i128)m2; // may exceed 64-bit for extreme cases
30     i128 res = (i128)r1 + (i128)m1 * (i128)t0;
31     ll L = (ll)lcm; // assumes lcm fits in 64-bit; safe for typical CF constraints
32     ll R = norm_mod((ll)(res % L), L);
33     return {R, L};
34 }
35 
36 // Solve x ≡ r[i] (mod m[i]) for i=0..n-1. Returns (r, M) or (0, -1) if no solution.
37 pair<ll,ll> crt(const vector<ll>& r, const vector<ll>& m){
38     ll R = 0, M = 1; // start with x ≡ 0 (mod 1)
39     for (size_t i = 0; i < r.size(); ++i) {
40         auto merged = crt_merge(R, M, r[i], m[i]);
41         if (merged.second == -1) return {0, -1};
42         R = merged.first; M = merged.second;
43     }
44     return {R, M};
45 }
46 
47 int main(){
48     // Example 1: pairwise coprime
49     vector<ll> r1 = {2, 3, 2};
50     vector<ll> m1 = {3, 5, 7};
51     auto sol1 = crt(r1, m1);
52     cout << "Solution: x ≡ " << sol1.first << " (mod " << sol1.second << ")\n";
53 
54     // Example 2: non-coprime but consistent
55     vector<ll> r2 = {1, 3};
56     vector<ll> m2 = {4, 6}; // gcd=2, 1 ≡ 3 (mod 2) -> consistent
57     auto sol2 = crt(r2, m2);
58     if (sol2.second == -1) cout << "No solution\n";
59     else cout << "Solution: x ≡ " << sol2.first << " (mod " << sol2.second << ")\n";
60 
61     // Example 3: inconsistent
62     vector<ll> r3 = {1, 2};
63     vector<ll> m3 = {4, 6}; // 1 !≡ 2 (mod 2)
64     auto sol3 = crt(r3, m3);
65     if (sol3.second == -1) cout << "No solution (inconsistent system)\n";
66 
67     return 0;
68 }
69

This implementation merges congruences one by one using the generalized CRT. It works even when moduli are not coprime, detecting inconsistency via gcd. To avoid overflow in intermediate products, we use __int128. The final modulus is lcm of all moduli if a solution exists.

Time: O(k log M) for k congruences and typical modulus size MSpace: O(1) extra aside from input storage

1	#include <bits/stdc++.h>
2	using namespace std;
3	using ll = long long;
4
5	// Internal helper: extended gcd on non-negative inputs only.
6	// Computes: returns g = gcd(a, b) >= 0 and finds x, y with ax + by = g.
7	static ll exgcd_nonneg(ll a, ll b, ll &x, ll &y) {
8	if (b == 0) { x = 1; y = 0; return a; }
9	ll x1, y1;
10	ll g = exgcd_nonneg(b, a % b, x1, y1);
11	// From: g = bx1 + (a%b)y1 = bx1 + (a - (a/b)b)y1 = ay1 + b(x1 - (a/b)y1)
12	x = y1;
13	y = x1 - (a / b) * y1; // safe: a,b >= 0 so C++ truncation equals floor
14	return g;
15	}
16
17	// Public wrapper: works for any signs of a, b. Ensures g >= 0 and ax + by = g.
18	ll extended_gcd(ll a, ll b, ll &x, ll &y) {
19	ll A = llabs(a), B = llabs(b);
20	if (A == 0 && B == 0) { x = 0; y = 0; return 0; } // convention
21	ll x0, y0;
22	ll g = exgcd_nonneg(A, B, x0, y0);
23	// Reapply signs so that ax + by = g
24	x = (a >= 0 ? x0 : -x0);
25	y = (b >= 0 ? y0 : -y0);
26	return g;
27	}
28
29	int main() {
30	// Example 1: basic test
31	ll a = 30, b = 18; ll x, y; ll g = extended_gcd(a, b, x, y);
32	cout << "gcd(" << a << ", " << b << ") = " << g << "\n";
33	cout << "Coefficients: x = " << x << ", y = " << y << "\n";
34	cout << "Check: ax + by = " << ax + by << "\n\n";
35
36	// Example 2: with negatives
37	a = -91; b = 35; g = extended_gcd(a, b, x, y);
38	cout << "gcd(" << a << ", " << b << ") = " << g << "\n";
39	cout << "Coefficients: x = " << x << ", y = " << y << "\n";
40	cout << "Check: ax + by = " << ax + by << "\n";
41	return 0;
42	}
43

1	#include <bits/stdc++.h>
2	using namespace std; using ll = long long; using i128 = __int128_t;
3
4	// Iterative extended Euclid working with non-negative a,b then reapply signs.
5	ll extended_gcd_iter(ll a, ll b, ll &x, ll &y) {
6	ll A = llabs(a), B = llabs(b);
7	ll old_r = A, r = B;
8	ll old_s = 1, s = 0; // coefficients for A
9	ll old_t = 0, t = 1; // coefficients for B
10	while (r != 0) {
11	ll q = old_r / r; // A,B >= 0 so this is floor
12	ll tmp;
13	tmp = old_r - q * r; old_r = r; r = tmp;
14	tmp = old_s - q * s; old_s = s; s = tmp;
15	tmp = old_t - q * t; old_t = t; t = tmp;
16	}
17	// old_r is gcd(A, B), and Aold_s + Bold_t = old_r
18	x = (a >= 0 ? old_s : -old_s);
19	y = (b >= 0 ? old_t : -old_t);
20	return old_r;
21	}
22
23	int main(){
24	ll a = 99, b = 78; ll x, y; ll g = extended_gcd_iter(a, b, x, y);
25	cout << "gcd("<<a<<","<<b<<")="<<g<<" with x="<<x<<", y="<<y<<"\n";
26	cout << "Check: " << ax + by << "\n";
27	// Compare to std::gcd
28	cout << "std::gcd gives: " << std::gcd(llabs(a), llabs(b)) << "\n";
29	return 0;
30	}
31

1	#include <bits/stdc++.h>
2	using namespace std; using ll = long long; using i128 = __int128_t;
3
4	// Extended GCD on non-negative a,b; returns g and finds x,y with ax + by = g.
5	static ll exgcd_nonneg(ll a, ll b, ll &x, ll &y){ if(b==0){x=1;y=0;return a;} ll x1,y1; ll g=exgcd_nonneg(b,a%b,x1,y1); x=y1; y=x1-(a/b)*y1; return g; }
6
7	// Solve m1 * p + m2 * q = g and also return g = gcd(m1,m2), with correct signs for m1,m2
8	static ll extended_gcd_signed(ll m1, ll m2, ll &p, ll &q){ ll A=llabs(m1), B=llabs(m2); ll x0,y0; ll g=exgcd_nonneg(A,B,x0,y0); p=(m1>=0?x0:-x0); q=(m2>=0?y0:-y0); return g; }
9
10	static ll norm_mod(ll x, ll m){ x%=m; if(x<0) x+=m; return x; }
11
12	// Safe multiply (a*b) mod m using 128-bit to avoid overflow
13	static ll mul_mod(ll a, ll b, ll m){ return (ll)((i128)a * (i128)b % (i128)m); }
14
15	// Merge two congruences: x ≡ r1 (mod m1), x ≡ r2 (mod m2)
16	// Returns (r, l) where solution set is x ≡ r (mod l). If no solution, l = -1.
17	static pair<ll,ll> crt_merge(ll r1, ll m1, ll r2, ll m2){
18	if (m1 == -1 \|\| m2 == -1) return {0, -1};
19	if (m1 == 0) return {norm_mod(r2, m2), m2};
20	if (m2 == 0) return {norm_mod(r1, m1), m1};
21	r1 = norm_mod(r1, m1); r2 = norm_mod(r2, m2);
22	ll p, q; ll g = extended_gcd_signed(m1, m2, p, q); // m1p + m2q = g
23	ll diff = r2 - r1;
24	if (diff % g != 0) return {0, -1}; // inconsistent
25	ll m2_g = m2 / g;
26	// t0 = (diff/g) * inv(m1/g mod m2/g). Here p is inverse of m1/g modulo m2/g.
27	ll t0 = mul_mod(diff / g, p, m2_g);
28	// New solution and modulus
29	i128 lcm = (i128)m1 / g * (i128)m2; // may exceed 64-bit for extreme cases
30	i128 res = (i128)r1 + (i128)m1 * (i128)t0;
31	ll L = (ll)lcm; // assumes lcm fits in 64-bit; safe for typical CF constraints
32	ll R = norm_mod((ll)(res % L), L);
33	return {R, L};
34	}
35
36	// Solve x ≡ r[i] (mod m[i]) for i=0..n-1. Returns (r, M) or (0, -1) if no solution.
37	pair<ll,ll> crt(const vector<ll>& r, const vector<ll>& m){
38	ll R = 0, M = 1; // start with x ≡ 0 (mod 1)
39	for (size_t i = 0; i < r.size(); ++i) {
40	auto merged = crt_merge(R, M, r[i], m[i]);
41	if (merged.second == -1) return {0, -1};
42	R = merged.first; M = merged.second;
43	}
44	return {R, M};
45	}
46
47	int main(){
48	// Example 1: pairwise coprime
49	vector<ll> r1 = {2, 3, 2};
50	vector<ll> m1 = {3, 5, 7};
51	auto sol1 = crt(r1, m1);
52	cout << "Solution: x ≡ " << sol1.first << " (mod " << sol1.second << ")\n";
53
54	// Example 2: non-coprime but consistent
55	vector<ll> r2 = {1, 3};
56	vector<ll> m2 = {4, 6}; // gcd=2, 1 ≡ 3 (mod 2) -> consistent
57	auto sol2 = crt(r2, m2);
58	if (sol2.second == -1) cout << "No solution\n";
59	else cout << "Solution: x ≡ " << sol2.first << " (mod " << sol2.second << ")\n";
60
61	// Example 3: inconsistent
62	vector<ll> r3 = {1, 2};
63	vector<ll> m3 = {4, 6}; // 1 !≡ 2 (mod 2)
64	auto sol3 = crt(r3, m3);
65	if (sol3.second == -1) cout << "No solution (inconsistent system)\n";
66
67	return 0;
68	}
69