Numbers and arithmetic · 2 of 4 Advanced
GCD and LCM
Find the greatest common divisor with Euclid's remainder steps, see why they work and how few they are, and compute the least common multiple without overflow.
- Divisibility Its GCD & LCM section gives the recursive form of the Euclidean algorithm, the Fibonacci worst case and the lcm overflow warning, followed by practice problems. usaco.guide (opens in a new tab)
- Euclidean algorithm for computing the greatest common divisor Proves the remainder step, states Lamé's theorem, which makes consecutive Fibonacci numbers the slowest inputs, and adds the lcm and the binary gcd. cp-algorithms.com (opens in a new tab)
- 最大公约数 (Greatest common divisor) Euclid’s algorithm and the subtraction method, the gcd and lcm of several numbers, and the extended algorithm that also finds coefficients. oi-wiki.org (opens in a new tab)