유클리드

널리 알려진 유클리드 호제법은 『원론』 제7권에 실려 있다. 『원론』은 기원전 300년에 그리스 수학자 유클리드가 쓴 책이다. 프톨레마이오스 왕이 『원론』을 훑어보고는 기하학을 배우는 더 짧은 길이 없겠냐고 기대를 담아 물었는데, 유클리드는 “기하학에 왕도는 없습니다”라고 단호하게 답했다는 이야기가 전해진다. 『원론』이 무려 열세 권이니 왕이 지름길을 찾은 것도 무리는 아니다. 이 책은 유클리드가 모아 정리한 수학 지식과 그가 직접 발견한 내용으로 이루어져 있다. 유클리드의 큰 업적은 그 재료를 하나의 유기적인 전체로 아름답게 체계화했다는 점이다. 『원론』은 이천 년 넘게 표준 교재 자리를 지켰다.

본래의 유클리드 호제법은 뺄셈만으로 두 양의 정수 $A$와 $B$의 최대공약수를 구한다. $A$와 $B$의 공약수가 $\min(A, B)$와 $\max(A, B) - \min(A, B)$의 공약수이기도 하다는 성질을 쓴다. 그래서 $A$와 $B$의 최대공약수를 다음과 같이 구한다.

1. $A = B$이면 최대공약수는 $B$이고, 알고리즘을 끝낸다.
2. $A$를 $\max(A, B) - \min(A, B)$로, $B$를 $\min(A, B)$로 바꾼다. 1번으로 돌아간다.

본래의 유클리드 호제법을 쓰든 다른 방법을 쓰든, 두 양의 정수의 최대공약수를 구하라.

$A = 24$, $B = 15$일 때 본래의 유클리드 호제법은 이런 순서로 값을 바꾼다.

1. $A = 24 - 15 = 9$, $B = 15$
2. $A = 15 - 9 = 6$, $B = 9$
3. $A = 9 - 6 = 3$, $B = 6$
4. $A = 6 - 3 = 3$, $B = 3$

즉 $\gcd(24, 15) = 3$이다.

입력은 한 줄이다. 이 줄에는 공백으로 구분한 두 양의 정수가 있고, 각 정수는 32767 이하이다.

주어진 두 양의 정수의 최대공약수를 정수 하나로 출력한다.