boj 2609 c++ 최대공약수와 최소공배수

boj 2609 c++ 최대공약수와 최소공배수

백준 2609 cpp 최대공약수와 최대공배수

 

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

 

처음 이 문제를 봤을 때 이런 생각을 했다.

하나만 풀려고 했는데 이건 너무 쉬우니까 오늘은 두 문제 풀어야겠네

그러나 결국엔 다른 사람의 코드를 보고야 말았다.

 

패배의 흔적

 

처음에는 i가 min(a, b)까지 돌면서 최대공약수를 찾고,

arr[10000000]을 선언해 (int i = 1; i * a < 100000000; i++)인 동안

최소공배수를 찾도록 했다.

그런데 아무리 시도해도 진행률 100%에서 테스트 케이스 하나를 통과를 못 하는 것이었다.

하다하다 도저히 되질 않아 남의 코드를 보았는데 ...

 

 

유클리드 호제법이라는 개념이 있더라.

최대공약수와 최대공약수를 이용한 최소공배수 구하는 법에 대한 공식이었다.

하 ... 이걸 미리 알았더라면 5분도 안 걸렸을 거 같은데 ........ 다음에 한번만 더 마주쳐라 최대공약수 최소공배수

 

아무튼 유클리드 호제법을 이용한 최대공약수 구하는 공식은 아래의 gcd함수와 같고, 재귀를 이용해서 구할 수도 있다.

최소공배수는 최대공약수를 이용해 구할 수 있는데, 아래의 lcm 함수와 같다.

 

#include <bits/stdc++.h>
using namespace std;

/*

int gcd(int a, int b)
{
    if (b == 0)
        return (a);
    return gcd(b, a % b);
}

*/

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

int lcm(int a, int b, int greatCommonDivisor)
{
    return (a * b) / greatCommonDivisor;
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);

    int a, b;
    cin >> a >> b;
    int greatCommonDivisor = gcd(a, b);
    int leastCommonMultiple = lcm(a, b, greatCommonDivisor);

    cout << greatCommonDivisor << '\n' << leastCommonMultiple;
}

 

ref - rebas.kr/639