고양이 두 잔

알고리즘을 풀다가 최대공약수를 구해야 하는 문제가 나와, 별생각 없이 순진하게 아래와 같이 풀었다. import sys a, b = map(int, sys.stdin.readline().split()) x = max(a, b) y = min(a, b) while x % y != 0: z = x % y x = y y = z print(a * b // y) 유클리드 호제법을 사용해서 간단하게 풀었다고 생각하고 넘어갔는데.. 혹시나 해서 검색해보니 역시나 파이썬 math 라이브러리에는 최대공약수와 최소공배수를 구해주는 함수가 있었다! 그것도 유클리드 호제법을 이용해 최적화가 되어 있는! 적잖이 김이 빠지지만, 사용 방법은 아래와 같다. import math # 최대공약수 print(math.gcd(35, 65..

문제 트럭을 타고 이동하던 상근이는 경찰의 검문을 받게 되었다. 경찰은 상근이가 운반하던 화물을 하나하나 모두 확인할 것이기 때문에, 검문하는데 엄청나게 오랜 시간이 걸린다. 상근이는 시간을 때우기 위해서 수학 게임을 하기로 했다. 먼저 근처에 보이는 숫자 N개를 종이에 적는다. 그 다음, 종이에 적은 수를 M으로 나누었을 때, 나머지가 모두 같게 되는 M을 모두 찾으려고 한다. M은 1보다 커야 한다. N개의 수가 주어졌을 때, 가능한 M을 모두 찾는 프로그램을 작성하시오. 입력 첫째 줄에 종이에 적은 수의 개수 N이 주어진다. (2 ≤ N ≤ 100) 다음 줄부터 N개 줄에는 종이에 적은 수가 하나씩 주어진다. 이 수는 모두 1보다 크거나 같고, 1,000,000,000보다 작거나 같은 자연수이다. ..

유클리드 호제법은 두 양의 정수, 혹은 다항식의 최대공약수를 구하는 알고리즘이다. 기원전 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의 최대공약수를 구한다고 해보자. 첫 계산은 다음과 같다..