Stage 2 · Lesson 2 of 7
GCD, LCM and Euclid's algorithm
The (gcd) of two numbers is the largest number that divides both. Euclid's algorithm finds it in O(log n) steps by repeatedly replacing the pair (a, b) with (b, a mod b), and C++ gives you gcd in the numeric header.
The least common multiple (lcm) is the smallest number both divide: a / gcd(a, b) * b. Many easy problems are gcd problems in disguise, such as making array elements equal with allowed subtractions, or finding when two repeating events line up. The gcd of a whole array is found by folding gcd over it.
Common trapcomputing lcm as a * b / gcd(a, b), where a * b overflows before the division happens.
A question to check yourself, an AI practice session and 1 cheat sheet entry come with the full roadmap. Unlock
Resources for this stage
Start with
- BookFreeCompetitive Programmer's Handbook
Antti Laaksonen · Beginner
Section 1.5 covers the maths basics and Chapter 21 covers number theory, from primes to modular inverses