백준 2609번 최대공약수와 최소공배수

< 백준 2609번 최대공약수와 최소공배수 - 마포 코딩박 >

사용한 알고리즘: 수학


 두 수 a, b 사이의 gcd 를 구하는 법을 묻는 문제였습니다.

a, b 사이의 gcd를 구하는 법은 다음과 같습니다.
b = a*D + R , D: 몫, R: 나머지 라고 한다면 a 와 a*D 의 gcd 는 a 이므로,
gcd(b,a) = gcd(a,R) 입니다.

따라서 gcd(b,a) = gcd(a, b%a) = .... 로 재귀적인 방법을 이용하여 gcd를 구해주면 됩니다.
한쪽이 0 이 나올때 까지 재귀를 계속 돌리면 됩니다.

a,b의 gcd = g 라 하면, a = g*A, b = g*B , ( A,B는 g 로 나누어지지 않는다 ) 이므로
a,b의 최소공배수는 A*B*g = (g*A*g*B)/g = a*b/g 입니다.