https://www.acmicpc.net/problem/2609 2609번: 최대공약수와 최소공배수 첫째 줄에는 입력으로 주어진 두 수의 최대공약수를, 둘째 줄에는 입력으로 주어진 두 수의 최소 공배수를 출력한다. www.acmicpc.net 유클리드 호제법(Euclidean Algorithm) 두 양의 정수 a,b (a>b)에 대하여 a=bq+r(0≤r gcd(a, b)=gcd(b, r) r=0이라면, a,b의 최대공약수는 b가 된다. (증명) gcd(a,b) = k a=nk b=mk a=bq+r nk=mkq+r r=(n-mq)k m과 n-mq 서로소라면 k는 최대공약수 (공통인수가 있다면 k는 최대공약수가 아님) (귀류법) 가정 [ m과 n-mq 서로소가 아니다. ] m = xG n-mg = yG ..