[백준 09924] The Euclidean Algorithm [Java]

문제

The famous Euclidean algorithm is found in Book VII of the Elements. The Elements was written in 300 B.C.~by the Greek mathematician Euclid. It is rumored that King Ptolemy, having looked through the Elements, hopefully asked Euclid if there were not a shorter way to geometry, to which Euclid severely answered: "In geometry there is no royal road!" Probably we should not blame the King for looking for short cuts, for there are thirteen books in the Elements\,! The books consist mainly of the mathematical knowledge amassed by Euclid, and possibly some discoveries of his own. The great achievement of Euclid is the beautifully systematic presentation of material as an organic whole. The Elements remained a standard work for over two thousand years. (see Episodes from the Early History of Mathematics, Asger Aaboe)

The modern Euclidean algorithm is often presented as

입력

The input consists of one line containing two positive integers (each not larger than 32767) separated by one or more spaces.

 

출력

The output consists of one line containing one integer.

---

풀이

유클리드 알고리즘을 이용해 GCD를 구하기 위해 몇번의 연산이 필요한지 세는 문제다.

a를 b로 나눈 몫을 누적해주며 GCD의 기저 사례까지 반복하면 쉽게 풀이할 수 있다.

---

소스코드

보기

---

출처

https://www.acmicpc.net/problem/9924