유클리드 호제법 - 위키백과, 우리 모두의 백과사전

Reference

유클리드 호제법

2개의 자연수의 최대공약수를 구하는 알고리즘

과정

1. $a>b$일때 $a$를 b로 나눈후 나머지를 $r$이라고 하자.
2. 이때, $a, b$의 최대공약수는 $b, r$의 최대공약수와 같다.

GCD구현 코드

입력 인수가 $a>b$이라는 것을 보장될 경우

int gcd(int a, int b) {
    return b ? gcd(b, a % b) : a;
}

입력인수의 크기 비교 없이 구할경우

int gcd(int a, int b) {
    return a % b ? gcd(b, a%b) : b;
}

응용

백준 2981번 : 검문

2981번: 검문

문제 요약

주어진 수들을 공통된 $m$으로 나눌 때 같은 나머지가 얻어지는 모든 $m$을 출력하는 문제이다.

풀이

나머지에 대해 다음과 같이 표현할 수 있다.