The greatest common divisor (GCD) is one of the oldest algorithms in mathematics, and it still shows up constantly in contest problems: simplifying fractions, synchronising cycles, and in clever tricks that turn a hard-looking problem into one line. This post covers how Euclid's algorithm works, why it is fast, and the LCM overflow trap.
Definitions
gcd(a, b) is the largest number that divides both a and b. lcm(a, b) is the smallest positive number that both a and b divide. For example gcd(12, 18) = 6 and lcm(12, 18) = 36. They are linked by a simple identity:
gcd(a, b) × lcm(a, b) = a × b
Euclid's algorithm
The key fact is gcd(a, b) = gcd(b, a mod b). Any number that divides both a and b also divides a − kb for any k, and a mod b is exactly such a number. The reverse also holds, so both pairs have the same common divisors and therefore the same greatest one.
Keep replacing the pair until the second number is 0. Then gcd(g, 0) = g.
Example for gcd(252, 105):
gcd(252, 105) -> 252 mod 105 = 42
gcd(105, 42) -> 105 mod 42 = 21
gcd(42, 21) -> 42 mod 21 = 0
gcd(21, 0) = 21Why it is fast
After two steps, the larger number always drops to less than half of what it was. So the number of steps is O(log min(a, b)), at most about 90 steps for numbers up to 1018. The slowest inputs are consecutive Fibonacci numbers, which is a fun fact worth remembering.
Code (C++)
This program reads n numbers and prints the GCD and LCM of all of them.
#include <bits/stdc++.h>
using namespace std;
long long gcd_ll(long long a, long long b) {
while (b != 0) {
long long r = a % b;
a = b;
b = r;
}
return a;
}
int main() {
int n;
cin >> n;
vector<long long> a(n);
for (auto &x : a) cin >> x;
long long g = 0, l = 1;
for (long long x : a) {
g = gcd_ll(g, x); // gcd(0, x) = x, so 0 is a safe start
l = l / gcd_ll(l, x) * x; // divide first to keep numbers small
}
cout << g << ' ' << l << '\n';
return 0;
}Since C++17 you can also use std::gcd and std::lcm from <numeric>. Writing it yourself once is still worth doing so you know what is inside.
The LCM overflow trap
The obvious formula a * b / gcd(a, b) multiplies first. For two numbers near 1010 the product is 1020, which overflows long long even though the LCM itself might be small. Dividing first, a / gcd(a, b) * b, avoids the giant intermediate value. The final LCM can still be too large to store if the numbers share few factors, so check the problem's limits.
Handy properties
- gcd(a, 0) = a, which makes 0 a safe starting value when taking the GCD of a list.
- The GCD of a list can be computed one element at a time: gcd(a, b, c) = gcd(gcd(a, b), c).
- gcd(a, b) = gcd(a, b − a). This lets you rewrite expressions like gcd(a1 + x, a2 + x, …) in terms of differences that do not depend on x, which is the whole trick behind Codeforces 1458A – Row GCD.
- For factorials, gcd(A!, B!) is just min(A, B)!, because the smaller factorial divides the larger one. That is all Codeforces 822A – I'm bored with life asks for.
Practice problems
- Codeforces 822A – I'm bored with life: a one-line observation about factorials.
- Codeforces 1458A – Row GCD: the difference trick above.
For more number theory, see the Lucky Division walkthrough.
