[유클리드 호제법] 최대공약수, 최소공배수 공식

이게 도대체 왜이렇게 안 외워지는지 모르겠다.

유클리드 호제법 (Euclidean algorithm)

최대공약수를 구하는 알고리즘

두 양의 정수 $a, b$ $(a>b)$ 에 대하여
$a = bq + r$ $(0$ $\leq$ $r<b)$ 이라 하면, $a, b$ 의 최대공약수는
$b, r$ 의 최대 공약수와 같다. 즉,

$r=0$ 이라면 $a, b$ 의 최대공약수는 $b$ 가 된다.

---

최대공약수 (GCD ; Greatest Common Divisor)

static long gcd(long a, long b) {
	if (b==0)    // r == 0 일 떄
        return a;    // b 가 최대공약수
	return gcd(b, a%b);
}

---

최소공배수 (LCM ; Least Common Multiple)

두 수의 곱 / 최대공약수

static long lcm(long a, long b) {
	return a*b/gcd(a,b);
}

---

관련문제
https://www.acmicpc.net/problem/13241