Skip to content

GCD & LCM

STL

cppreference

#include <numeric>

-std=c++17

template< class M, class N >
constexpr std::common_type_t<M, N> gcd( M m, N n );

template< class M, class N >
constexpr std::common_type_t<M, N> lcm( M m, N n );

GCD 1

int gcd(int x, int y) {
    return y>0 ? gcd(y, x%y) : x;
}

int gcd(int x, int y) {
    while (y^=x^=y^=x%=y);
    return x;
}

LCM 2

int lcm(int x, int y) {
    return a / gcd(x, y) * y;
}

Tips

Performing division before multiplication can help avoid overflow.

  1. Greatest Common Divisor ↩

  2. Least Common Multiple ↩

Comments