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.
-
How many solutions with x, y ≥ 0 does
3·x + 5·y = 100have?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. -
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. -
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. -
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). -
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
- 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).
- 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.
- What is its complexity? O(log min(a, b)), the same as Euclid's algorithm.
- Given one solution, describe all of them. x + k·(b/g), y − k·(a/g) for every integer k.
- How do you get the smallest non-negative x? x mod (b/g), adding b/g if negative (C++
%keeps the sign). - 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.
- Where can this overflow, and how do you prevent it? x0·(c/g) can reach ~10^27: multiply in
__int128and 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.