정올 1002 : 최대공약수, 최소공배수 응용

** 두 수의 곱 = 두 수의 최대공약수 * 최소공배수

유클리드 호제법 이용

<두 개의 숫자만 주어진 상황> 조건: A>B

두 수 A와 B의 최대공약수 = B와 r(A를 B로 나눈 나머지)의 최대공약수

 

즉, GCD(A,B) = GCD(B,r)

ex> GCD(30,18) = GCD(18,12) = GCD(12,6) = GCD(6,0)

 

<여러개의 숫자가 주어진 상황>

두개의 숫자만 주어진 상황과 비슷한 형식으로 진행하면 된다.

예를 들어 두 개의 수 A와 B의 최대공약수를 D라고 하면, 세 개의 수 A,B,C의 최대공약수는 D와 C의 최대공약수와 같다.

아래는 재귀함수를 이용하여 구현해보았다.

 

최소공배수를 구하는 경우도 같은 방법으로 진행된다.

두 수 A,B가 주어졌을 때, A와 B의 곱 = A와 B의 최대공약수 * A와 B의 최소공배수 이다.

즉, lcm(A,B) = (A*B) / GCD(A,B) 

여러개의 숫자가 주어졌을 때도 같은 방법으로 적용하면 된다.

 

#include <stdio.h>
#include <stdlib.h>

int GCD(int x, int y) {
	if (y == 0)return x;
	return GCD(y, x % y);

}

int main() {
	int n;
	int gcd, lcm;
	scanf("%d", &n);
	int* arr = (int*)malloc(sizeof(int) * n);
	for (int i = 0; i < n; i++) {
		scanf("%d", &arr[i]);
	}
   
	gcd = lcm = arr[0];
	for (int i = 1; i < n; i++) {
		gcd = GCD(gcd, arr[i]);          // 재귀이용 
		lcm = (lcm * arr[i]) / GCD(lcm, arr[i]);   
	}

	printf("%d %d", gcd,lcm);
	free(arr);
    
    return 0;
}