시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 128 MB | 320 | 158 | 138 | 51.111% |
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
But the original Euclidean algorithm uses subtraction instead of division. It is based on the observation that a common divisor of the positive integers $A$, $B$ is also a common divisor of the integers $\min(A,B)$, $\max(A,B)-\min(A,B)$. Thus the gcd of two positive integers can be found as
For example, given $A = 24, B = 15$, the original Euclidean algorithm produces
That is, before finding $\gcd(24,15) = 3$, the original Euclidean algorithm has to execute Step 3 four times.
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.
24 15
4