[백준/BOJ] 1934번: 최소공배수 ( 유클리드 호제법 ) - C++ 문제 풀이

문제 설명

 

문제 링크: https://www.acmicpc.net/problem/13241

 

풀이

이 문제는 두 숫자를 입력받아 최소공배수( least common multiple )를 구하는 문제입니다.

 

양의 정수 a와 b의 최소공배수는 

최소공배수 = a * b /  최대공약수

입니다.

 

그런데, 이 문제에서는 a * b의 값이 $10^{16}$의 범위를 가지므로, int 타입을 사용하면, 결과 값을 담을 수 없게 됩니다.

따라서, 적어도 long 보다 큰 범위를 가진 타입의 숫자를 사용해야 합니다.

 

여기서는 문제에서 주어진 타입인 long long int를 사용합니다.

그런데, 매번 이 긴 타입을 입력하는 것은 불편한 일입니다.

 

C++은 이럴 때를 대비하여 타입의 별명을 만들 수 있습니다.

using mtype = long long int;	// mtype이 long long int의 별명

 

위에 사용한 using 구문에 관한 내용은 여기에서 볼 수 있습니다.

[C++] 별명을 만드는 typedef와 using

 

이제, 최대공약수( greatest common divisor )만 구하면 됩니다.

최대공약수는 유클리드 호제법을 사용합니다.

 

유클리드 호제법은

양의 정수 a, b, r에 대하여, 

a % b = r 일 때, a와 b의 최대공약수는 b와 r의 최대공약수이다

 

라는 정의를 사용하여, 두 숫자 a, b의 최대공약수를 구하는 방법입니다.

 

1. 큰 수 a를 작은 수 b로 나누는 mod 연산을 수행합니다.

2. 위의 나누는 값 b와 mod 연산의 결과 r로 다시 mod 연산을 수행합니다.

3. mod 연산의 결과 r이 0이 나올 때까지 2의 과정을 반복합니다.

4. mod 연산의 결과가 0이 될 때, b의 값이 최대공약수입니다.

 

예를 들어, 326과 150의 최대공약수는,

326 % 150 = 26
150 % 26 = 20
  26 % 20 = 6
  20 % 6 = 2
    6 % 2 = 0

위의 과정을 거쳐서 2가 최대공약수가 됩니다.

 

이를 코드로 작성하면 다음과 같습니다.

using mtype = long long int;

// 최대공약수를 구하는 함수
mtype gcd(mtype a, mtype b){

    if ( b > a){
        swap(a, b);
    }

    mtype r = a % b;

    while( r != 0 ){
        a = b;
        b = r;
        r = a % b;
    }
    return b;
}

 

 

소스 코드

#include <iostream>
using namespace std;

using mtype = long long int;

mtype gcd(mtype a, mtype b){

    if ( b > a){
        swap(a, b);
    }

    mtype r = a % b;

    while( r != 0 ){
        a = b;
        b = r;
        r = a % b;
    }
    return b;
}

int main(){

    mtype a, b;
    cin >> a >> b;

    mtype ret = gcd( a, b); // 최대공약수

    cout << a * b / ret;    // 최대공배수

    return 0;
}