GCD와 LCM의 경계값 처리

네이버 블로그에 작성한 GCD, LCM (2025-05-08)를 바탕으로 설명과 예제를 보완했다.

최대공약수 GCD와 최소공배수 LCM은 공식 자체보다 입력 범위에서 실수하기 쉽다. 재귀식에서 0으로 나머지 연산을 하거나, LCM 계산 중 정수 범위를 넘기거나, 최솟값에 abs를 적용하는 문제가 대표적이다.

유클리드 호제법의 종료 조건

음수가 아닌 정수에 대해 다음 관계를 반복한다.

gcd(a, b) = gcd(b, a % b)  (b가 0이 아닐 때)
gcd(a, 0) = a

따라서 %를 계산하기 전에 b가 0인지 검사해야 한다. 반복문에서는 while (b != 0)이 그 조건이다. (0, 0)은 C++ 표준 라이브러리의 계약과 맞춰 결과를 0으로 다룬다.

표준 라이브러리를 사용할 때도 범위 확인하기

C++17의 <numeric>에 std::gcd와 std::lcm이 있다. 음수도 받을 수 있지만 인자의 절댓값이 결과 타입에 표현 가능해야 한다. LCM은 최종 결과도 표현 가능해야 한다. 이를 어겼을 때 자동으로 예외나 오류 코드를 돌려주는 인터페이스가 아니다.

예를 들어 32비트 부호 있는 입력은 먼저 64비트 타입으로 넓힌 뒤 절댓값과 결과를 다루는 방법을 선택할 수 있다. 부호 있는 타입의 최솟값은 같은 타입으로 양수 표현이 불가능할 수 있으므로 abs(INT_MIN)을 일반적인 음수 처리처럼 쓰지 않는다.

곱셈 전에 LCM 범위 검사하기

다음 C++17 예제는 음수가 아닌 std::uint64_t 입력을 받는다. LCM이 타입 범위를 넘으면 std::nullopt를 반환한다.

#include <cstdint>
#include <iostream>
#include <limits>
#include <numeric>
#include <optional>

using U64 = std::uint64_t;

U64 euclid(U64 a, U64 b) {
    while (b != 0) {
        const U64 remainder = a % b;
        a = b;
        b = remainder;
    }
    return a;
}

std::optional<U64> lcm_checked(U64 a, U64 b) {
    if (a == 0 || b == 0) return U64{0};
    const U64 reduced = a / std::gcd(a, b);
    if (reduced > std::numeric_limits<U64>::max() / b) {
        return std::nullopt;
    }
    return reduced * b;
}

int main() {
    std::cout << euclid(48, 18) << '\n';
    std::cout << *lcm_checked(21, 6) << '\n';
    std::cout << *lcm_checked(0, 10) << '\n';
    const auto large = lcm_checkedmax(), 2;
    std::cout << (large ? "fits" : "overflow") << '\n';
    std::cout << std::gcdint64_t{-48}, std::int64_t{18} << '\n';
}

c++ -std=c++17 -Wall -Wextra -pedantic gcd-lcm.cpp -o gcd-lcm
./gcd-lcm

6
42
0
overflow
6

알려진 작은 상수 예제 두 개는 결과가 존재하므로 역참조했다. 일반 입력에서는 if (result)처럼 값의 존재를 먼저 확인한다.

a / gcd(a, b) * b는 먼저 나누기 때문에 불필요하게 큰 중간 곱을 피하지만, 최종 결과의 오버플로까지 없애지는 않는다. 위 코드는 곱셈 전 max / b와 비교하며, b가 0인 경우는 앞에서 반환한다.

고정 폭 정수에서 나머지 연산 비용을 상수로 보면 유클리드 호제법은 양수 입력에 대해 O(log(min(a,b))) 단계다. 임의 정밀도 정수에서는 각 나머지 연산의 비용까지 별도로 고려해야 한다.

자료: C++ gcd 계약, C++ lcm 계약