[백준/C++] 13241 최소공배수 (S5)

유형	난이도	완료일	링크	특이사항
정수론	실버5	23/03/19	https://www.acmicpc.net/problem/13241

내 코드

#include <iostream>
#include <algorithm>

using namespace std;

int main(void)
{
    long long int a, b;
    cin >> a >> b;
    
    long long int x = max(a,b);
    long long int y = min(a,b);
    
    long long int temp;
    long long int k;
    
    while(true)
    {
        temp = x%y;
        if(temp == 0)
        {
            k = y;   
            break;
        }
        else
        {
            x = y;
            y = temp;
        }
        
      //  cout <<"ok\\n";
    }
    
    long long int ans = a*b/k;
    cout << ans;
    
    return 0;
}

 정수론의 기초 최소공배수 구하기이다. 막무가내로 하나씩 수를 대입하여 푸는 방식도 있지만 당연히 매우 비효율적이다. 유클리드 호제법을 사용하여 빠르게 해결할 수 있다. 전에도 이런 문제를 푼 적이 있지만 왜 이렇게 풀리는 것인지 깊게 생각해보지 않고 그냥 공식을 따라 코드만 작성하고 말았던 것 같다. 유클리드 호제법이 왜 성립하는지 생각해보자.

두 양의 정수 a, b (a≥b)가 있을 때 이 두 수의 최대공약수를 G라고 하면, a= AG, b= BG( G가 최대공약수이므로 A, B는 서로소이다. )라고 할 수 있다.

 a를 b로 나누면 a= q(몫)b+r(나머지)로 표현할 수 있고 이는 AG = qBG+r, G(A-qB) = r과 같다.

이 때 b= BG이므로 r = G(A-qB), b = BG로 나머지인 r과 b 사이에 G라는 공통약수가 생긴다.

B와 A-qB가 서로소이면 G가 b, r의 최대공약수가 되므로 a % b = n이고 n ≠ 0일 때 a와 b의 최대공약수는 b, n 의 최대공약수라는 유클리드 호제법이 증명된다.

B와 A-qB가 서로소가 아니라고 가정하고 공통약수 t를 가지는 꼴로 바꿔 표현해보면,

B = nt, A-qB = mt가 되고 A = mt+qnt = t(m+gn)으로 나타낼 수 있다.

 그러나 이렇게 되면 B = nt, A = (m+gn)t로 서로소인 A, B가 t라는 공통약수를 가지는 모순된 결과를 낳는다. 따라서 B 와 A-qB는 서로소고 G가 b, r의 최대공약수인 것이다.

최소공배수는 두 수를 곱한 후 최대공약수로 나눠주면 바로 구할 수 있으므로(a * b, c * b 일 때 a * b * b * c / b 가 최소공배수이다) 최대공약수만 빠르게 구해주면 최소공배수도 바로 구해진다.

최대공약수/최소공배수는 다양하게 응용되므로 꼭 기억해둬야겠다.