Why this matters when you build with AI
Ask an AI tool for an lcm function and it often writes a * b / gcd(a, b). That line is correct on paper and wrong in a 64-bit program: the product a * b can be far larger than the answer, and it overflows before the division happens. The result is a wrong number with no error message. Ask for a linear equation solver and the same tool often forgets that C++ integer division rounds toward zero, so a negative answer comes out one step off.
You can catch both problems in a minute if you know the standard shapes. This lesson gives those shapes in C++17 and shows how to test them against a brute force program, which is a slow program that tries every candidate and is easy to trust.
Two terms first. The greatest common divisor (gcd) of two numbers is the largest number that divides both. The least common multiple (lcm) is the smallest positive number that both divide. For 12 and 18, the gcd is 6 and the lcm is 36.
The idea: Euclid's algorithm
The gcd rule that makes everything fast is this. If b is not zero, then gcd(a, b) = gcd(b, a mod b), where mod is the remainder after division. The reason is that any number dividing both a and b also divides a - q*b for any whole number q, and that is exactly the remainder a mod b when q is the quotient. When b reaches zero, the answer is the number that is left.
Worked example, gcd of 252 and 198:
252 mod 198 = 54 so gcd(252, 198) = gcd(198, 54)
198 mod 54 = 36 so gcd(198, 54) = gcd(54, 36)
54 mod 36 = 18 so gcd(54, 36) = gcd(36, 18)
36 mod 18 = 0 so gcd(36, 18) = gcd(18, 0) = 18This is the same trace printed by a short Python program. It is input free, so the site can run it:
Real output of that program:
252 mod 198 = 54
198 mod 54 = 36
54 mod 36 = 18
36 mod 18 = 0
gcd = 18Why the number of steps is small
Look at any two steps. Call the remainders r0 > r1 > r2 > .... We have r(k+2) < r(k) / 2. Proof: if r(k+1) is at most half of r(k), then r(k+2) is smaller than r(k+1), so it is also below half. If r(k+1) is more than half of r(k), then r(k+2) = r(k) - r(k+1), which is less than half of r(k). Either way, every two steps cut the value at least in half.
So for b up to 10^18 the loop runs at most about 2 * log2(b) + 2, roughly 120 steps. The actual worst case is consecutive Fibonacci numbers, where each step only just makes progress. The next program uses F(42) = 267914296 and F(41) = 165580141:
gcd(267914296, 165580141) takes 40 stepsForty steps for numbers near 2.7 * 10^8 is well inside the bound of about 58 for that size. A Python run of the same pair also counted 40 steps. Euclid's algorithm runs in O(log min(a, b)) time, which means the number of steps grows with the number of digits, not with the size of the numbers.
The C++ code
std::gcd and std::lcm in <numeric> exist from C++17. Use them when you can. Knowing the hand-written version matters for two reasons: you need the same loop for the extended version below, and older judges or your own tests may not have the standard functions.
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
// Euclid: gcd(a, b) = gcd(b, a mod b), with gcd(a, 0) = a.
ll gcd_euclid(ll a, ll b) {
while (b != 0) {
ll r = a % b;
a = b;
b = r;
}
return a;
}
// lcm without overflow: divide first, then multiply.
ll lcm_safe(ll a, ll b) {
if (a == 0 || b == 0) return 0;
return a / gcd_euclid(a, b) * b;
}The lcm trap
The lcm is a * b / gcd(a, b). The product a * b is computed first, so it can overflow even when the lcm fits. In C++, signed overflow is undefined behaviour, which means the compiler may do anything. The safe order is a / gcd(a, b) * b: the division first makes the number smaller, and the result is the true lcm, which is what you want when it fits in 64 bits.
The demo below uses unsigned types for the wrong version, so the wrap-around can be printed. Here a = 4 * 10^9 and b = 6 * 10^9. The true lcm is 1.2 * 10^10, which fits easily.
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main() {
ll a = 4000000000LL, b = 6000000000LL;
// Signed overflow is undefined behaviour, so the wrapped value is shown with unsigned types.
unsigned long long ua = a, ub = b;
unsigned long long naive = ua * ub / std::gcd(ua, ub);
ll safe = a / std::gcd(a, b) * b;
cout << "naive lcm wraps to " << naive << " (unsigned)\n";
cout << "safe lcm = " << safe << "\n";
return 0;
}Real output, compiled with g++ -std=c++17 -O2:
naive lcm wraps to 2776627963 (unsigned)
safe lcm = 12000000000The naive answer is about 2.8 * 10^9 and is wrong by a factor of more than four. Nothing in the output warns you about it, which is why this bug survives code review.
The extended Euclidean algorithm
Euclid gives the gcd. The extended version also gives two whole numbers x and y such that a * x + b * y = gcd(a, b). These are called Bezout coefficients, after Étienne Bézout, and they can be negative. Example: for a = 240 and b = 46, the gcd is 2, and x = -9, y = 47 gives 240 * (-9) + 46 * 47 = -2160 + 2162 = 2.
The method is a recursion on the same steps as Euclid. Suppose the call on (b, a mod b) returns x1 and y1 with b * x1 + (a mod b) * y1 = g. Replace a mod b by a - (a / b) * b. Then a * y1 + b * (x1 - (a / b) * y1) = g. So the pair for (a, b) is x = y1 and y = x1 - (a / b) * y1.
// Returns g = gcd(a, b) and sets x, y so that a*x + b*y = g.
// Assumes a >= 0 and b >= 0.
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;
}Real output of a demo that calls ext_gcd and prints the check value:
ext_gcd(240, 46): g = 2, x = -9, y = 47, check = 2
ext_gcd(6, 9): g = 3, x = -1, y = 1, check = 3The check value should equal the gcd every time. If it does not, your recursion has a sign error, which is the most common mistake with this function.
Solving a * x + b * y = c
A linear equation a * x + b * y = c has integer solutions only when gcd(a, b) divides c. Let g = gcd(a, b). If c mod g is not zero, there are none. Otherwise, take the extended result for (a, b) and multiply it by c / g. That gives one particular solution (x0, y0).
All solutions then come from adding multiples of b / g to x and subtracting the same multiples of a / g from y. Write A = a / g and B = b / g. The solutions are x = x0 + k * B and y = y0 - k * A for every integer k.
For the smallest non-negative x, reduce x0 into the range [0, B). Then y follows from y0 = (c - a * x0) / b, which divides exactly.
To count solutions with 0 <= x <= X and 0 <= y <= Y, find the range of k that keeps both values inside their boxes. Each bound becomes a division, and the division must round the right way for negative numbers. C++ integer division rounds toward zero, so -7 / 2 is -3, not -4. The helper functions below round down and up correctly.
The full exercise solution
Input: five integers a b c X Y on one line, with 1 <= a, b <= 10^9, |c| <= 10^9 and 0 <= X, Y <= 10^9. Output: the first line is x y for the smallest non-negative solution, or -1 if there is none. The second line is the number of solutions in the box. The second line is missing when the first is -1.
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
// Returns g = gcd(a, b) and sets x, y so that a*x + b*y = g. Assumes a, b >= 0.
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;
}
// Floor and ceiling division that are correct for negative numbers. Requires b > 0.
ll floor_div(ll a, ll b) {
ll q = a / b;
if ((a % b != 0) && (a < 0)) q--;
return q;
}
ll ceil_div(ll a, ll b) {
ll q = a / b;
if ((a % b != 0) && (a > 0)) q++;
return q;
}
// Result in [0, m) for m > 0.
ll pos_mod(ll a, ll m) {
ll r = a % m;
return r < 0 ? r + m : r;
}
int main() {
ll a, b, c, X, Y;
cin >> a >> b >> c >> X >> Y;
ll x1, y1;
ll g = ext_gcd(a, b, x1, y1);
if (c % g != 0) {
cout << -1 << "\n";
return 0;
}
ll A = a / g, B = b / g, C = c / g;
// One particular solution, with x moved into [0, B).
ll x0 = pos_mod(x1 * C, B); // |x1| <= 10^9 and |C| <= 10^9, so the product fits in 64 bits
ll y0 = (c - a * x0) / b; // exact division
cout << x0 << " " << y0 << "\n";
// All solutions: x = x0 + k*B, y = y0 - k*A.
// 0 <= x0 + k*B <= X gives k in [ceil(-x0/B), floor((X - x0)/B)].
ll lo = ceil_div(-x0, B), hi = floor_div(X - x0, B);
// 0 <= y0 - k*A <= Y gives k*A <= y0 and k*A >= y0 - Y.
lo = max(lo, ceil_div(y0 - Y, A));
hi = min(hi, floor_div(y0, A));
cout << (hi >= lo ? hi - lo + 1 : 0) << "\n";
return 0;
}Real output on small inputs. The first two lines are from the program and the examples were chosen to cover a solution, a no-solution case and a negative c:
input: 6 9 15 10 10
1 1
1
input: 7 13 1 100 100
2 -1
0
input: 6 9 -3 10 10
1 -1
0
input: 6 9 4 10 10
-1Check the first line by hand: 6 * 1 + 9 * 1 = 15. The second: 7 * 2 + 13 * (-1) = 1, and no pair with both x and y non-negative fits. The solutions are x = 2 + 13k and y = -1 - 7k, and y >= 0 needs k <= -1 while x >= 0 needs k >= 0.
How this was tested
The program above was compiled with g++ -std=c++17 -O2 -Wall -Wextra and compared with a brute force program. The brute force tries every x in [0, b/g) for the smallest solution and every pair in the box for the count. The comparison ran on 1,500 random inputs with a and b up to 60, c between -80 and 80, and boxes up to 25. There were 0 mismatches. The ext_gcd helper was also checked on 300,000 random pairs up to 2 * 10^9: the identity a*x + b*y = g held every time, and g matched std::gcd. The lcm function matched std::lcm on those pairs too.
Complexity
Euclid, extended Euclid and lcm_safe each take O(log min(a, b)) time and O(1) extra memory for the iterative loop. The extended recursion uses one stack frame per step. By the bound above, inputs up to 10^9 need at most about 62 steps, so the stack depth is small.
Common mistakes
Overflow in lcm. The symptom is a lcm that is too small or negative, as in the 2776627963 example above. Fix: divide by the gcd before multiplying.
Wrong sign with negative numbers. In C++, % takes the sign of the left operand, so -7 % 3 is -1, not 2. Code that tests x % m == 0 still works, but code that uses x % m as an index does not. Use pos_mod when you need a value in [0, m).
Rounding a negative division down. -7 / 2 is -3 in C++. A bound such as k >= (-x0) / B can therefore be off by one when x0 is positive. Use ceil_div and floor_div.
Using the extended function with negative inputs. The code above assumes a and b are zero or positive. With a negative input, the gcd it returns can be negative, and the c % g check and the box counts then go wrong. Make a and b positive before you solve, and handle the signs of x and y afterwards.
Forgetting the divisibility check. If c is not a multiple of g, there is no solution. Dividing anyway gives a fraction that C++ silently truncates, and the program prints a wrong pair. The symptom is a pair (x, y) that fails a*x + b*y = c when you substitute it back.
Checklist to keep
- Compute
lcmasa / gcd(a, b) * b, nevera * b / gcd(a, b). - Use
long longfor every value that multiplies another value. - After
ext_gcd, checka*x + b*y == gon a sample. - Before solving
a*x + b*y = c, checkc % g == 0. - Reduce
x0into[0, B)before multiplying it bya. - Use floor and ceiling helpers whenever a bound involves a negative numerator.
- Test every formula against a brute force on small random inputs before trusting it.
Hands-on exercise
Write the brute force first. It should try every x in [0, X] and every y in [0, Y], and also search for the smallest non-negative x among the first b / g values. Then write the fast version, and compare them on at least 1,000 random inputs with small values. Keep the random seed fixed so a failure can be repeated.
Then run the fast version on the largest allowed input, a = 999999937, b = 999999929, c = 10^9, X = Y = 10^9, and record how long it takes on your machine. The loops in this lesson do a few dozen steps, so a result that takes seconds means a loop you did not expect.
A good answer prints the same two lines as the brute force on every test, and the fast program finishes the large test quickly. Check the solutions by substituting them back into a*x + b*y = c, not only by comparing with the brute force, because a shared bug can fool both.
Prompt to try with an AI tool
Use this prompt, then check the answer with the steps above:
Write a C++17 function that returns the lcm of two positive numbers up to 5 * 10^9 each.
Assume the lcm fits in a 64-bit signed integer. Use long long, and explain in two sentences
why the division must come before the multiplication. Then give three test inputs with the
expected output for each.A good answer uses a / gcd(a, b) * b, explains that the division keeps the intermediate value at most the lcm, and includes the test 4000000000 6000000000, with the expected output 12000000000. Check the code for a * b / gcd(a, b), which fails that test.
Practice
These take a few minutes each. Try them on paper or in your scratch folder before opening the answers.
Practice 1: gcd by hand
Find gcd(462, 1071) with Euclid's steps, and say how many steps it takes.
Hint: Divide the larger number by the smaller, then repeat with the smaller number and the remainder.
Show the answer
The steps are 1071 mod 462 = 147, 462 mod 147 = 21 and 147 mod 21 = 0. So gcd(462, 1071) = 21, found in 3 steps. Check: 462 = 2 * 3 * 7 * 11 and 1071 = 3 * 3 * 7 * 17, and their common part is 3 * 7 = 21.
Practice 2: all solutions of 462x + 1071y = 21
Find one solution, then describe all of them.
Hint: The gcd is 21, so divide every number by 21 before you work out the step size of x.
Show the answer
The extended Euclid gives x = 7, y = -3, and 462 * 7 + 1071 * (-3) = 3234 - 3213 = 21. Dividing by the gcd gives A = 22 and B = 51. All solutions are x = 7 + 51k and y = -3 - 22k for any integer k. Check with k = 1: x = 58, y = -25, and 462 * 58 + 1071 * (-25) = 26796 - 26775 = 21.
Practice 3: lcm of a list without overflow
Write a function that takes a list of up to 100 numbers, each up to 10^9, and returns their lcm. Assume the result fits in 64 bits.
Hint: The lcm of three numbers is the lcm of the first two, combined with the third.
Show the answer
ll lcm_list(const vector<ll> &v) {
ll result = 1;
for (ll x : v) result = result / gcd_euclid(result, x) * x;
return result;
}The division happens before the multiplication, so the intermediate value never exceeds the final lcm. The starting value 1 is the identity for lcm.
Practice 4: count pairs in a box
Count the pairs with 0 <= x <= 20 and 0 <= y <= 20 that satisfy 3x + 5y = 8.
Hint: Try small values of y and see which x is left.
Show the answer
The only pair is x = 1, y = 1. The program prints 1 1 and then 1 for the input 3 5 8 20 20, which matches the hand count.
Practice 5: why the count is zero
Explain in plain words why the input 6 9 -3 10 10 gives zero solutions in the box, even though it has a solution with x = 1 and y = -1.
Hint: The solutions move in steps of 3 for x and go down by 2 for y each time, so check which direction keeps y non-negative.
Show the answer
The solutions are x = 1 + 3k and y = -1 - 2k. To keep y >= 0, k must be at most -1, which makes x negative. No k keeps both x and y non-negative, so the box count is zero. The program prints 1 -1 for the smallest non-negative x, then 0.
Summary
The gcd comes from Euclid's remainder loop, which takes about 2 log2(b) steps at most. The lcm must be computed as a / gcd * b so that it does not overflow. The extended version returns coefficients that give a*x + b*y = gcd, and that solves any linear equation with integer answers when the gcd divides the right side. Test every formula against a brute force, since the common bugs are silent wrong answers rather than crashes.
Sources and scope
Euclid's algorithm and its extended form are standard material. Donald E. Knuth, The Art of Computer Programming, Volume 2: Seminumerical Algorithms, first published in 1969, covers the Euclidean algorithm in its section on greatest common divisors. The step bound and the Fibonacci worst case were derived above and checked on the numbers shown. The C++ results come from g++ 15.2.0 on Linux with -std=c++17 -O2, and the Python samples come from Python 3 on the same machine. The bounds on C++ integer division and on % are language rules, not measurements.