[알고리즘/C++] 최대공약수, 최소공배수

- 최대공약수(GCD, Greatest Common Divisor)는 두 수를 공통으로 나눌 수 있는 최대의 정수를, 최소공배수는 두 수의 배수가 되는 최소의 정수이다.
- 최대공약수 계산의 경우, 유클리드 호제법과 재귀함수를 이용하여 구현할 수 있다.

int gcd(int a, int b){
	return b ? gcd(b, a % b) : a;
}

- 임의의 수 A, B의 최대공약수가 G라면, A=aG, B=bG로 표현할 수 있다고 할 때,
- (a - kb)G = c 형태로 관계식을 나타낼 수 있다. 이때 a-kb와 b의 최대공약수가 G이기 위해 두 수는 서로소여야 하고, 이 조건을 만족할 때 b와 c의 최대공약수는 G가 된다.

- 위의 재귀 코드는 다음과 같이 동작한다.
  - 먼저 a, b를 받아서, b의 값이 참인지를 (= 존재하는지) 확인한다. (약수 계산이므로 a, b는 모두 2 이상임을 가정한다.)
  - gcd는 b와 a/b의 나머지를 매개변수로 받아 gcd 함수를 다시 호출한다.
  - 이 과정을 반복할 때 두 수 사이의 공통된 약수가 있다면, gcd(a,b)함수의 b에는 언젠가 0이 전달된다.
  - b=0이 전달되는 시점에서 해당 함수에 전달된 a값이 최대공약수로 반환되게 된다.
  - 만약 두 수가 서로소라면(ex. 2, 3), 마지막에는 a%b에 1이 전달될 것이므로, 최소공배수가 1이 전달된다.

- 두 수 a, b의 최소공배수는 a * b / G로 계산 가능하다.

int g = gcd(a, b);
int lcm = a * b / g;

//오버플로우 방지
int g = gcd(a, b);
int lcm = a / g * b / g * g;

위 코드로 간편히 풀 수 있지만, 곱셈 연산은 오버플로우의 우려가 있으므로, 경우에 따라 아래 코드로 계산할 수 있다.