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

2609. 최대공약수와 최소공배수

문제

두 개의 자연수를 입력받아 최대 공약수와 최소 공배수를 출력하는 프로그램을 작성하시오.

입력

첫째 줄에는 두 개의 자연수가 주어진다. 이 둘은 10,000이하의 자연수이며 사이에 한 칸의 공백이 주어진다.

출력

첫째 줄에는 입력으로 주어진 두 수의 최대공약수를,둘째 줄에는 입력으로 주어진 두 수의 최소 공배수를 출력한다.

예제 입력 

24 18

예제 출력 

6
72

컴퓨터는 거대하고 빠른 계산기므로 이런 수학적 기초가 되는 연산을 빠르게 해낼 의무가 있다!

또한 컴퓨터를 다루는 사람은, 계산기에게 효율적인 명령을 내려야 한다.

당연히, 최대공약수를 알아야 최소공배수를 알 수 있다. 나의 상식선에선 그렇다.

초딩 때 최대공약수를 구하는 방법을 떠올려보면, 두 숫자 모두가 서로소가 될 때 까지, 두 수를 모두 나눌 수 있는 숫자로 계속 나눈다.

그러면 여태껏 나눈 숫자들을 곱하면 최대공약수고, 서로소 숫자 까지 곱하면 최소공배수다.

계산기에게 이런 계산을 맡기려면 어떻게 해야 할까?

물론 나이브하게 2부터 계속 키워가면서 나눠버리는 방법도 있다. 당연히 최악의 경우 두 수가 서로소면 O(n)이 걸릴테고.

그래서 유클리드가 만든 유클리드 호제법을 가져다 쓰기로 한다. 다음과 같다.

a>b인 두 수에 대해,   a%b = r 이라면, gcd(a,b) = (b,r) 이다.

예를 들어 gcd(1071, 1029) = gcd(1029, 42) = gcd(42, 21) = gcd(21, 0) = 21이다.

증명은 다음을 참고. 

https://ko.wikipedia.org/wiki/%EC%9C%A0%ED%81%B4%EB%A6%AC%EB%93%9C_%ED%98%B8%EC%A0%9C%EB%B2%95#.EC.95.8C.EA.B3.A0.EB.A6.AC.EC.A6.98

또한 시간 복잡도는 여러 수학적 증명을 거쳐 O(log(n))임이 밝혀졌다. n의 비트수만큼 걸리는 것이다.

구현에 대해선, 당연히 재귀적으로 땡겨 쓸 직관이 생긴다!

코드 : 

#include <stdio.h>
using namespace std;
 
int a, b;
 
int gcd(int a, int b) {
    if (a % b == 0)
        return b;
    else
        return gcd(b, a%b);
}
 
int main() {
    scanf("%d %d", &a, &b);
    int g = a > b ? gcd(a, b) : gcd(b, a);
    printf("%d\n%d", g, a*b / g);
    return 0;
}