[백준 2436 C++][G5] 공약수

⭐️ 난이도

 

Gold 5

---

⭐️ 문제

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

2436번: 공약수

 

---

⭐️ Idea flow

 

이 문제는 GCD와 LCM의 특징을 이용하여 풀 수 있는 문제였다. 

 

문제에서 어떤 두 자연수 A와 B의 최소 공배수(LCM)과 최대 공약수(GCD)가 주어지는데, 이 때, 두 자연수를 구해야 하는 문제였다.

처음에 떠올린 식은 A * B = GCD(A, B) * LCM(A, B) 였다.

문제에서 lcm과 gcd가 주어지기 때문에 두 수를 곱하면 A*B를 구할 수 있다. 그럼 A*B를 소인수분해하여 소인수를 두 수에게 적당히 분배를 잘하면 될 것이라고 생각했다.

하지만 소인수를 분배 하는 것이 생각보다 쉽지 않아서 다른 방법을 생각해야 했다.

 

 

다른 방법이 도저히 생각나지 않아서 다른 블로그의 도움을 살짝 받았다.

 

찾아야하는 두 자연수를 A와 B라고 했을 때, 최대 공약수를 G, 최소 공배수를 L이라고 가정하자.

1. 우선 최대 공약수 G는 A와 B의 공통 약수이다.

   따라서 a와 b가 서로소 일 때, A = aG, B = bG 임을 알 수 있다.

 

2. L은 최소 공배수 이기 때문에, L = a * b * G가 성립한다.

   이해가 안된다면 직접 해보자. 30와 36의 L(최소공배수)는 180이고, G(최대공약수)는 6이다.

   이 때, 180(최소공배수) = 5 * 6 * 6(최대공약수)가 성립한다.

 

3. 위의 식을 변형하면 L/G = a * b임을 알 수 있다.

 

4. 따라서 서로소인 a와 b를 구하고, 그 값들에 G(최대공약수)를 곱하면 우리가 원하는 값을 찾을 수 있다.

 

 

 

[전체적인 알고리즘]

1. LCM과 GCD를 입력받고, LCM / GCD를 구한다. 이 값을 divide라고 하자.

 

2. divide의 약수들을 구한다. 1부터 sqrt(divide)까지 반복문을 통해 검사한다.

 

3. 이 때, divide를 검사하는 수로 나누었을 때 나누어 떨어진다면 약수를 찾았다는 이야기이다.

 

4. 두 수가 서로소 인지 확인한다. 두 수가 서로소인 것은 두 수를 공통적으로 나눌 수 있는 값이 1 말고 없다는 뜻이다.

   즉, 두 수의 최대 공약수가 1이면 서로소이다. 경우 수가 여러 개 라면 그 중 두 수의 합이 제일 작은 것을 저장한다.

 

5. 합이 제일 작은 두 서로소에 최대 공약수(GCD)를 곱하면 우리가 찾던 수이다.

 

 

---

⭐️ Code

#include <iostream>
#include <algorithm>
#include <string>
#include <cstring>
#include <cmath>
#include <vector>

#define INF 987654321
using namespace std;

// 2436 - 공약수
long long int gcd, lcm;
long long int resultA = 0, resultB = 0;

void input(){
    cin >> gcd >> lcm;
}

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

void solve(){
    long long int divide = lcm / gcd;

    for(int i = 1; i <= sqrt(divide); i++){
        if(divide % i == 0){ // 나누어 떨어진다면 약수 pair를 찾을 수 있다.
            long long int a = i, b = divide/i;

            // 최대 공약수가 1이라는 뜻은 서로소라는 뜻
            if(getGCD(a, b) == 1){
                resultA = a;
                resultB = b;
            }
        }
    }

    cout << resultA * gcd << ' ' << resultB * gcd;
}

int main(){

    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    input();
    solve();

    return 0;
}

 

---

⭐️ Feedback

 

이번 문제를 통해 알게된 것들

 

1. 두 자연수 A와 B, 그리고 GCD(최대공약수)와 LCM(최소공배수)의 관계는 이러하다.

    A * B = GCD(A, B) * LCM(A, B)

 

2. 최대 공약수를 G라고 할 때, A = aG, B = bG로 표현할 수 있으며

   이 때 a와 b는 서로소여야 한다. (그렇지 않으면 최대 공약수가 G보다 큰 수가 된다)

 

3. 2번에 이어서 최소 공배수를 L이라고 할 때, L = a * b * G로 표현할 수 있다.

 

4. L / G = a * b도 성립한다.

 

5. n의 약수를 찾을 때, 1부터 sqrt(n)까지의 수를 탐색하면 충분하며, 이 때 찾게 되는 약수의 짝(pair)의 합은 점점 작아진다.