[2609번] 최대공약수와 최소공배수

문제 출처 :

https://www.acmicpc.net/problem/2609

알고리즘 분석 :

문제 해결에 필요한 사항

1. GCD / LCM 구하는 법

GCD :: 최대 공약수는 아래 GCD function으로 구할 수 있다. 보통 학교에서 배우는 방식과는 다르지만

직접 손으로 적어보면 이 방식도 존재한다는 것을 알 수 있다.

LCM :: 최소 공배수는 GCD(a, b)*(a/ GCD(a, b))*(b/ GCD(a, b))  방식으로 구할 수 있다.

문제 자체는 어렵지 않지만, 최대 공약수와 최소 공배수가 필요한 상황에 적절히 이용할 수 있기에 문제 풀이를 해두려 한다.

소스 코드 : 

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
 
int GCD(int max, int min)
{
    if (min == 0)
        return max;
 
    else
        return GCD(min, max % min);
}
 
 
int main()
{
    int a, b, tmp;
    
 
    scanf("%d %d", &a, &b);
 
    // 무조건 a를 max, b를 min으로 스왑해주는 과정
    b > a ? tmp = b, b = a, a = tmp : 0;
 
    // GCD(a, b)*(a/ GCD(a, b))*(b/ GCD(a, b))는 LCM 구하는 방법
    printf("%d\n%d", GCD(a, b), GCD(a, b)*(a/ GCD(a, b))*(b/ GCD(a, b)));
 
    return 0;
}
 
//                                                       This source code Copyright belongs to Crocus
//                                                        If you want to see more? click here >>