백준 2436 공약수 (C++)

2436번: 공약수

정수론을 이용한 문제이다. 먼저 공식에 대해 알고 있어야 한다. 두 수 A, B가 있을 때, A = a * GCD(A,B), B = b * GCD(A,B)을 만족하는 a, b가 있다고 하자. 이럴 경우 LCM(A,B) = a * b * GCD(A,B)가 성립하게 된다. 이는 LCM * GCD = a * b가 된다. 즉 LCM * GCD를 만족하는 a와 b를 찾아주면 된다. 반복문을 돌며 div의 약수들을 구해 두 수의 gcd가 1일 경우 값을 저장해준다. 이 때 두 수의 합이 최소인 경우에 저장을 해주면 된다. 이 후 이를 출력해주었다. 수의 범위가 커서 어떻게 접근해야 할지 아이디어가 떠오르지 않아 블로그를 참고했다. 이러한 방식에 대해서도 알아두어야 겠다.

#include <iostream>

using namespace std;

long long n1, n2;
long long result1 = 987654321, result2 = 987654321;

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

void solution() {
    long long div = n2 / n1;

    for (long long i = 1; i * i <= div; i++) {
        if (div % i == 0) {
            long long a = i;
            long long b = div / i;

            if (gcd(a, b) == 1 && a + b < result1 + result2) {
                result1 = a;
                result2 = b;
            }
        }
    }

    cout << result1 * n1 << " " << result2 * n1;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);

    cin >> n1 >> n2;

    solution();

    return 0;
}