SyntaxPilot
Courses/Competitive Programming/Lesson 25

Competitive Programming · Lesson 25 of 90 · 16 min

Extended Euclid and linear Diophantine equations

queued

These are the notes for Competitive Programming episode 25 (number theory). A college canteen sells only 7- and 11-rupee coupons and never gives change: can you pay exactly 100? Trying every count works by hand, but in the original problem Exact Change the bill goes up to 10^18 and the same loop gets Time Limit Exceeded. We find out when there is no answer at all (the gcd must divide the bill), run Euclid's algorithm from episode 19 backwards to write the gcd as a·x + b·y (the extended Euclidean algorithm), fix the negative coupons it gives by swapping coupons, guard the multiplication with __int128, and pass a stress test. As a bonus, the same function gives the modular inverse for any modulus, where Fermat's trick from episode 22 silently fails. Every C++ example was compiled with g++ -O2 -std=c++17 main.cpp -o main (g++ 13, the same command as the SyntaxPilot compiler); all outputs below are real.

The real-life hooks

Canteen coupons. Coupons come in 7 and 11 rupees, the bill is 100, and there is no change. 0 sevens leave 100, 1 leaves 93, 2 leave 86 … 8 sevens (56) leave 44 = 4 elevens. So 8 sevens and 4 elevens. A bill of 20 can't be paid at all: 20, 13 and 6 are not multiples of 11.

Only even bills. With 4- and 6-rupee coupons, every total 4x + 6y = 2(2x + 3y) is even. A bill of 25 is impossible, and you know it without trying a single count.

A delivery rider. Ride out stop by stop, noting every turn, then come home undoing the turns in reverse. Euclid's algorithm is the ride out (gcd(a, b) → gcd(b, a % b) → … → b = 0); the extended algorithm is the ride back, building the answer at each stop.

Swapping coupons. 11 sevens and 7 elevens are both worth 77. Hand over 11 more sevens and 7 fewer elevens and the total doesn't change: that's how one answer turns into every answer.

A linear Diophantine equation

7·x + 11·y = 100 is

  • linear: x and y are only multiplied by fixed numbers (never x², never x·y);
  • Diophantine (after Diophantus, a Greek mathematician): x and y must be integers (whole numbers, possibly negative).

For coupons we also need x ≥ 0 and y ≥ 0, a non-negative solution.

Problem K · Exact Change

Problem K · Exact Change (written for this course). Coupons are worth a and b rupees. Pay exactly c rupees. Print x y with a·x + b·y = c, x ≥ 0, y ≥ 0 and the smallest possible x; if it can't be done, print -1.

Input: a b c. 1 ≤ a, b ≤ 10^9, 0 ≤ c ≤ 10^18, time limit 1 second.

Sample input Sample output Why
7 11 100 8 4 56 + 44 = 100
4 6 25 -1 4x + 6y is always even
4 6 26 2 3 8 + 18 = 26
7 11 20 -1 gcd is 1, but the smallest x = 6 already costs 42 > 20
5 3 0 0 0 paying nothing takes no coupons

Brute force: try every x (Time Limit Exceeded)

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int main() {
    ll a, b, c;
    cin >> a >> b >> c;
    for (ll x = 0; a * x <= c; x++)
        if ((c - a * x) % b == 0) {
            cout << x << " " << (c - a * x) / b << "\n";
            return 0;
        }
    cout << -1 << "\n";
    return 0;
}

7 11 100 → 8 4. 4 6 1000000000000000001 → Time Limit Exceeded: there is no answer, so the loop tries every x up to c / 4 ≈ 2.5·10^17.

When is there no answer? The gcd

Any number that divides both a and b also divides a·x + b·y. The biggest such number is the gcd (greatest common divisor, episode 19). So:

a·x + b·y = c has an integer solution  ⇔  gcd(a, b) divides c

The "⇐" half is Bezout's identity (after the French mathematician Étienne Bézout): for any a, b there are integers x, y with a·x + b·y = gcd(a, b). Example: 7·(−3) + 11·2 = 1 = gcd(7, 11). The extended Euclidean algorithm finds those x and y.

The extended Euclidean algorithm

Euclid: gcd(a, b) = gcd(b, a % b), and gcd(a, 0) = a.

Bottom (b = 0): a·1 + 0·0 = a, so x = 1, y = 0.

One step back up. The call below solved b·x1 + (a % b)·y1 = g. Since a % b = a − (a / b)·b (integer division):

b·x1 + (a − (a/b)·b)·y1 = g
a·y1 + b·(x1 − (a/b)·y1) = g
⇒ x = y1,  y = x1 − (a/b)·y1

Trace for (7, 11) (calls go down, answers come back up):

Call (a, b) a % b (x, y) returned Check
(7, 11) 7 (−3, 2) 7·(−3) + 11·2 = 1
(11, 7) 4 (2, −3) 22 − 21 = 1
(7, 4) 3 (−1, 2) −7 + 8 = 1
(4, 3) 1 (1, −1) 4 − 3 = 1
(3, 1) 0 (0, 1) 0 + 1 = 1
(1, 0) – (1, 0) base case
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

ll ext_gcd(ll a, ll b, ll &x, ll &y) {
    if (b == 0) { x = 1; y = 0; return a; }
    ll x1, y1;
    ll g = ext_gcd(b, a % b, x1, y1);
    x = y1;
    y = x1 - (a / b) * y1;
    return g;
}

int main() {
    ll a, b, x, y;
    cin >> a >> b;
    ll g = ext_gcd(a, b, x, y);
    cout << "g=" << g << " x=" << x << " y=" << y << "\n";
    return 0;
}

7 11 → g=1 x=-3 y=2. 4 6 → g=2 x=-1 y=1 (−4 + 6 = 2).

It makes exactly as many calls as Euclid's algorithm: O(log min(a, b)), under 100 for numbers up to 10^9.

Scaling to c, and the negative-coupon problem

Multiply 7·(−3) + 11·2 = 1 by 100: 7·(−300) + 11·200 = 100. In general multiply x0, y0 by c / g.

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

ll ext_gcd(ll a, ll b, ll &x, ll &y) {
    if (b == 0) { x = 1; y = 0; return a; }
    ll x1, y1;
    ll g = ext_gcd(b, a % b, x1, y1);
    x = y1;
    y = x1 - (a / b) * y1;
    return g;
}

int main() {
    ll a, b, c, x, y;
    cin >> a >> b >> c;
    ll g = ext_gcd(a, b, x, y);
    if (c % g != 0) { cout << -1 << "\n"; return 0; }
    cout << x * (c / g) << " " << y * (c / g) << "\n";
    return 0;
}

7 11 100 → -300 200. A true equation, but −300 coupons is impossible.

Every solution: swapping coupons

11 sevens = 7 elevens = 77. So if (x, y) works, so does (x + 11, y − 7). In general, with g = gcd(a, b):

x = x0·(c/g) + k·(b/g),   y = y0·(c/g) − k·(a/g),   k any integer

and these are all the solutions. We divide by g so the swap is as small as possible (for 4 and 6: 3 fours = 2 sixes = 12, not 6 fours = 4 sixes).

x (7s) −300 … −14 −3 8 19
y (11s) 200 … 22 15 4 −3

Smallest x ≥ 0: x = x0·(c/g) mod (b/g), then add b/g if it came out negative (in C++ % keeps the sign: −300 % 11 = −3). Any bigger x only lowers y, so if y = (c − a·x) / b is negative for the smallest x, there is no non-negative solution.

Overflow: x0 can be about 10^9 and c / g about 10^18; their product (≈10^27) overflows long long. Multiply in __int128 (holds about ±1.7·10^38) and take % step before converting back.

The accepted solution

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

ll ext_gcd(ll a, ll b, ll &x, ll &y) {
    if (b == 0) { x = 1; y = 0; return a; }
    ll x1, y1;
    ll g = ext_gcd(b, a % b, x1, y1);
    x = y1;
    y = x1 - (a / b) * y1;
    return g;
}

int main() {
    ll a, b, c, x0, y0;
    cin >> a >> b >> c;
    ll g = ext_gcd(a, b, x0, y0);
    if (c % g != 0) { cout << -1 << "\n"; return 0; }
    ll step = b / g;                 // x moves in steps of b/g
    ll x = (ll)((__int128)x0 * (c / g) % step);
    if (x < 0) x += step;            // smallest x >= 0
    ll rest = c - a * x;             // what the 11s must pay
    if (rest < 0) { cout << -1 << "\n"; return 0; }
    cout << x << " " << rest / b << "\n";
    return 0;
}
Input Output
7 11 100 8 4
4 6 25 -1
4 6 26 2 3
7 11 20 -1
5 3 0 0 0
4 6 1000000000000000001 -1 (instant; brute force: TLE)
999999937 1000000007 1000000000000000000 100000000 900000000
1 1 1000000000000000000 0 1000000000000000000

Stress test

Brute force against the formula on 1000 random small cases (coupons 1 … 12, bills 0 … 79), from episode 5:

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

ll ext_gcd(ll a, ll b, ll &x, ll &y) {
    if (b == 0) { x = 1; y = 0; return a; }
    ll x1, y1;
    ll g = ext_gcd(b, a % b, x1, y1);
    x = y1;
    y = x1 - (a / b) * y1;
    return g;
}

ll brute(ll a, ll b, ll c) {
    for (ll x = 0; a * x <= c; x++)
        if ((c - a * x) % b == 0) return x;
    return -1;
}
ll fast(ll a, ll b, ll c) {
    ll x0, y0, g = ext_gcd(a, b, x0, y0);
    if (c % g) return -1;
    ll s = b / g, x = x0 * (c / g) % s;
    if (x < 0) x += s;
    return a * x <= c ? x : -1;
}
int main() {
    mt19937 rng(25);
    for (int t = 1; t <= 1000; t++) {
        ll a = rng() % 12 + 1, b = rng() % 12 + 1, c = rng() % 80;
        if (brute(a, b, c) != fast(a, b, c)) {
            cout << a << " " << b << " " << c << " failed";
            return 0;
        }
    }
    cout << "all 1000 tests passed";
}

Real output: all 1000 tests passed.

Bonus: the modular inverse for any modulus

The inverse of a mod m is a number v with a·v % m = 1 (episode 22). Fermat's little theorem gives v = a^(m−2) mod m, but only when m is prime:

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

ll power(ll a, ll e, ll m) {
    ll r = 1;
    for (a %= m; e > 0; e >>= 1, a = a * a % m)
        if (e & 1) r = r * a % m;
    return r;
}

int main() {
    ll a, m;
    cin >> a >> m;
    ll inv = power(a, m - 2, m);    // Fermat: m must be prime!
    cout << "inv=" << inv << " check=" << a * inv % m << "\n";
    return 0;
}

3 10 → inv=1 check=3: wrong, with no warning (10 isn't prime). 3 11 → inv=4 check=1 (11 is prime).

a·v ≡ 1 (mod m) means a·v + m·k = 1 for some integer k: a linear Diophantine equation with c = 1. So run extended Euclid on (a, m). If the gcd is 1, the inverse is x mod m (made non-negative); otherwise there is no inverse.

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

ll ext_gcd(ll a, ll b, ll &x, ll &y) {
    if (b == 0) { x = 1; y = 0; return a; }
    ll x1, y1;
    ll g = ext_gcd(b, a % b, x1, y1);
    x = y1;
    y = x1 - (a / b) * y1;
    return g;
}

int main() {
    ll a, m, x, y;
    cin >> a >> m;
    if (ext_gcd(a, m, x, y) != 1) {
        cout << "no inverse\n";
        return 0;
    }
    ll inv = (x % m + m) % m;
    cout << "inv=" << inv << " check=" << a * inv % m << "\n";
    return 0;
}
Input Output Why
3 10 inv=7 check=1 3·7 = 21 ≡ 1
4 10 no inverse gcd(4, 10) = 2: 4·v is always even
7 1000000006 inv=571428575 check=1 works for a non-prime modulus

Complexity vs the constraints

Approach Time Worst case here Verdict
Try every x O(c / a) 2.5·10^17 tries TLE
Extended Euclid + one shift O(log min(a, b)) under 100 steps instant
Inverse with extended Euclid O(log m) any modulus instant
Inverse with Fermat O(log m) prime m only wrong for m = 10

Memory: O(log min(a, b)) for the recursion. The running time does not depend on c.

Common mistakes (and the real outputs)

Bug 1: never shifting a negative x

    ll x = (ll)((__int128)x0 * (c / g) % step);
    // missing: if (x < 0) x += step;

7 11 100 → -3 11 (expected 8 4). In C++, −300 % 11 = −3. The equation holds (−21 + 121 = 100), but −3 coupons is impossible.

Bug 2: multiplying in long long

    ll x = x0 * (c / g) % step;      // no __int128

999999937 1000000007 1000000000000000000 → 264850878 735149133 (expected 100000000 900000000). Those coupons add up to 999999999460438617, not 10^18: the product overflowed and wrapped around.

Bug 3: no gcd check

    ll g = ext_gcd(a, b, x0, y0);
    // missing: if (c % g != 0) { cout << -1 << "\n"; return 0; }

4 6 25 → 0 4 (expected -1). 4 sixes = 24, not 25: c / g silently dropped the remainder.

Summary table

Mistake What you see Why Fix
no shift after % -3 11 instead of 8 4 % keeps the sign in C++ if (x < 0) x += step;
x0 * (c / g) in long long coupons worth 999999999460438617 10^9 · 10^18 overflows (__int128)x0 * (c / g)
no c % g check 0 4 for 4 6 25 integer division drops the remainder print -1 if c % g != 0
Fermat with m = 10 inv=1 check=3 Fermat needs a prime modulus ext_gcd(a, m, x, y)
for (ll x = 0; a * x <= c; x++) Time Limit Exceeded up to 2.5·10^17 tries extended Euclid

Mini project

Write a small number-theory header: ext_gcd, solve(a, b, c) returning the smallest non-negative solution (or none), countSolutions(a, b, c), and inverse(a, m) for any m. Stress-test every function against brute force for all a, b ≤ 30 and c ≤ 300, and the inverse for all a < m ≤ 200.

Practice

These follow the video's homework.

  1. How many solutions with x, y ≥ 0 does 3·x + 5·y = 100 have?

    Answer Smallest x = 0 (y = 20); x grows in steps of 5 while y = (100 − 3x)/5 ≥ 0, so x = 0, 5, …, 30: <b>7</b> solutions (checked by brute force). In general: count = (x_max − x_min) / step + 1, where x_max is the x for the smallest non-negative y.

  2. Pay 100 with 3- and 5-rupee coupons using the fewest coupons in total.

    Answer Each swap trades 5 threes for 3 fives (2 fewer coupons), so use as many fives as possible: <b>0 threes, 20 fives</b> (20 coupons). The totals for the 7 solutions are 20, 22, …, 32.

  3. Solve 3·x ≡ 6 (mod 12) and print every x in [0, 12).

    Answer g = gcd(3, 12) = 3 divides 6, so there are g = 3 answers, spaced 12 / 3 = 4 apart: <b>2, 6, 10</b> (checked by brute force). If g didn't divide 6 there would be none.

  4. Find the inverse of 7 mod 30 by hand with extended Euclid.

    Answer 30 = 4·7 + 2, 7 = 3·2 + 1. Back up: 1 = 7 − 3·2 = 7 − 3·(30 − 4·7) = 13·7 − 3·30. So the inverse is <b>13</b> (7·13 = 91 = 3·30 + 1).

  5. Can 12- and 18-rupee coupons pay exactly 1000?

    Answer <b>No.</b> gcd(12, 18) = 6 and 1000 is not a multiple of 6 (checked by brute force).

Quick quiz

Coupons of 6 and 10 rupees. Which bill can be paid exactly?

A) 7 · B) 14 · C) 26 · D) 33

Answer

C. 26 = 6·1 + 10·2. 7 and 33 are odd, but gcd(6, 10) = 2. 14 is the trap: it's even, so integer solutions exist, but the smallest non-negative x is 4 and 4·6 = 24 > 14 (checked by brute force).

Interview questions

  1. When does a·x + b·y = c have integer solutions? Exactly when gcd(a, b) divides c (Bezout's identity gives the gcd itself; scale by c / g).
  2. Derive the extended Euclid recurrence. From b·x1 + (a % b)·y1 = g and a % b = a − ⌊a/b⌋·b: x = y1, y = x1 − ⌊a/b⌋·y1; base case (1, 0) when b = 0.
  3. What is its complexity? O(log min(a, b)), the same as Euclid's algorithm.
  4. Given one solution, describe all of them. x + k·(b/g), y − k·(a/g) for every integer k.
  5. How do you get the smallest non-negative x? x mod (b/g), adding b/g if negative (C++ % keeps the sign).
  6. How do you compute a modular inverse when m isn't prime? Extended Euclid on (a, m); the inverse exists iff gcd(a, m) = 1 and equals x mod m.
  7. Where can this overflow, and how do you prevent it? x0·(c/g) can reach ~10^27: multiply in __int128 and reduce mod b/g first.

Glossary

Term Meaning Example
Integer A whole number, positive, zero or negative −300, 0, 8
Linear equation Variables only multiplied by fixed numbers 7x + 11y = 100
Diophantine equation An equation whose answers must be integers coupons can't be split
Non-negative Zero or more x ≥ 0
gcd Greatest common divisor: the biggest number dividing both gcd(4, 6) = 2
Euclid's algorithm gcd(a, b) = gcd(b, a % b) until b = 0 gcd(7, 11) → … → gcd(1, 0) = 1
Bezout's identity a·x + b·y = gcd(a, b) always has integer solutions 7·(−3) + 11·2 = 1
Extended Euclidean algorithm Euclid's algorithm that also returns those x and y ext_gcd(7, 11) → (1, −3, 2)
Integer division Division that drops the remainder 11 / 7 = 1
Modulo (%) The remainder; in C++ it keeps the sign of the left side −300 % 11 = −3
Overflow A result too big for its type wraps around to a wrong value 10^9 · 10^18 in long long
__int128 GCC's 128-bit integer, up to about 1.7·10^38 (__int128)x0 * (c / g)
Modular inverse v with a·v ≡ 1 (mod m) 3·7 = 21 ≡ 1 (mod 10)
Fermat's little theorem For prime p: a^(p−1) ≡ 1, so a^(p−2) is the inverse wrong for m = 10
Stress test Comparing a fast solution with brute force on many random small inputs all 1000 tests passed

Summary

  • a·x + b·y = c has integer solutions only when gcd(a, b) divides c: check that first.
  • Extended Euclid writes the gcd as a·x + b·y in O(log min(a, b)): x = y1, y = x1 − (a/b)·y1, base (1, 0).
  • Scale by c / g; all solutions differ by k·(b/g) in x and −k·(a/g) in y.
  • The smallest x ≥ 0 is x mod (b/g), shifted up if negative; if its y is negative, there's no answer.
  • Multiply in __int128. The same function gives the modular inverse for any modulus when gcd(a, m) = 1.
  • Next: the Chinese remainder theorem, which merges remainders with extended Euclid.

Solutions in C++, Java and Python

Problem K · Exact Change

C++

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

ll ext_gcd(ll a, ll b, ll &x, ll &y) {
    if (b == 0) { x = 1; y = 0; return a; }
    ll x1, y1;
    ll g = ext_gcd(b, a % b, x1, y1);
    x = y1;
    y = x1 - (a / b) * y1;
    return g;
}

int main() {
    ll a, b, c, x0, y0;
    cin >> a >> b >> c;
    ll g = ext_gcd(a, b, x0, y0);
    if (c % g != 0) { cout << -1 << "\n"; return 0; }
    ll step = b / g;                 // x moves in steps of b/g
    ll x = (ll)((__int128)x0 * (c / g) % step);
    if (x < 0) x += step;            // smallest x >= 0
    ll rest = c - a * x;             // what the 11s must pay
    if (rest < 0) { cout << -1 << "\n"; return 0; }
    cout << x << " " << rest / b << "\n";
    return 0;
}

Java (BigInteger.mod is never negative, so no shift is needed)

import java.util.*;
import java.math.BigInteger;

public class Main {
    static long x, y;                       // filled by extGcd
    static long extGcd(long a, long b) {
        if (b == 0) { x = 1; y = 0; return a; }
        long g = extGcd(b, a % b);
        long x1 = x, y1 = y;
        x = y1;
        y = x1 - (a / b) * y1;
        return g;
    }
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        long a = in.nextLong(), b = in.nextLong(), c = in.nextLong();
        long g = extGcd(a, b);
        if (c % g != 0) { System.out.println(-1); return; }
        long step = b / g;
        long xs = BigInteger.valueOf(x).multiply(BigInteger.valueOf(c / g))
                            .mod(BigInteger.valueOf(step)).longValue();   // mod() is never negative
        long rest = c - a * xs;
        if (rest < 0) { System.out.println(-1); return; }
        System.out.println(xs + " " + rest / b);
    }
}

Python (integers never overflow and % is never negative)

import sys

def ext_gcd(a, b):
    if b == 0:
        return a, 1, 0
    g, x1, y1 = ext_gcd(b, a % b)
    return g, y1, x1 - (a // b) * y1

a, b, c = map(int, sys.stdin.read().split())
g, x0, y0 = ext_gcd(a, b)
if c % g:
    print(-1)
else:
    step = b // g
    x = x0 * (c // g) % step      # Python's % is never negative, no overflow
    rest = c - a * x
    print(-1 if rest < 0 else f"{x} {rest // b}")

All three print the same output on every input in the table above.