gcd — std::gcd
gcd — std::gcd (최대공약수)
std::gcd는 두 정수 m과 n의 **최대공약수(greatest common divisor)**를 계산해요. C++17에서 도입됐어요.
<numeric> 헤더에 있어요.
출처: cppreference
본문
// <numeric> 헤더, C++17
template< class M, class N >
constexpr std::common_type_t<M, N> gcd( M m, N n );
m과 n의 최대공약수를 계산해요.
만약 M 또는 N이 정수 타입이 아니거나, (cv 한정) bool이면 프로그램은 잘못된 형태(ill-formed)예요.
만약 |m| 또는 |n|이 std::common_type_t<M, N> 타입의 값으로 표현될 수 없으면 동작이 정의되지 않아요.
#include <numeric>
#include <iostream>
std::gcd(12, 18); // 6
std::gcd(0, 5); // 5 (gcd(0, n) = n)
std::gcd(7, 13); // 1 (서로소)
std::gcd(-12, 18); // 6 (부호 무시, 항상 음이 아닌 결과)
특징
- constexpr — 컴파일 타임에도 사용 가능 (
static_assert에 활용). - 결과는 항상 음이 아닌 정수예요.
- 서로 다른 정수 타입을 인자로 받아
std::common_type_t로 통일해요. gcd(0, 0)은 0이에요.
// 컴파일 타임 사용
static_assert(std::gcd(12, 18) == 6);
// 분수 약분에 활용
int g = std::gcd(num, den);
num /= g; den /= g;
숫자 이론, 분수 단순화, 최소공배수(lcm) 구현 등에 널리 쓰여요.