고양이 두 잔

유클리드 호제법은 두 양의 정수, 혹은 다항식의 최대공약수를 구하는 알고리즘이다. 기원전 300년에 그리스의 수학자 유클리드에 의해 기술된 이 알고리즘은 인류 최초의 알고리즘이라는 호칭도 가지고 있다. 그 내용은 다음과 같다. 유클리드 호제법 두 양의 정수 a, b(a > b)에 대하여 a = bq + r (0 ≤ r < b)이라 하면, a, b의 최대공약수는 b, r의 최대공약수와 같다. 즉, gcd(a, b) = gcd(b, r)이다. 이때 r = 0이라면, a, b의 최대공약수는 b가 된다. 쉽게 말하면 큰 숫자를 작은 숫자로 나누고, 그 나머지로 작은 숫자를 나누는 계산을 나머지가 0이 될 때까지 반복하는 것이다. 예를 들어 1096과 411의 최대공약수를 구한다고 해보자. 첫 계산은 다음과 같다..