[2436] 공약수

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

문제에서 인풋으로 GCD와 LCM을 줍니다.

우리는 그렇다면

어떤 수 a, b가 있다고 존재할 때

A = a / GCD

B = b / GCD

라고 한다면

LCM = GCD * A * B

라는 것을 알 수 있습니다.

여기서 가장 중요한 조건 ! A와 B는 서로소여야만 한다는 것입니다.

서로소라는 것은 두 수는 약수를 1만을 가진다는 것인데요.

이 조건을 만족하지 않으면 A와 B는 후보가 될 수 없습니다.

예륻 들어 GCD가 4라는 인풋이 들어왔는데 A가 2 B가 4라면

더 나눌 수 있는 수가 존재하므로 후보가 아니라는 말이죠.

그 외에는 어려운 부분은 없었습니다.

#include <iostream>
#include <vector>
#include <queue>
#include <cmath>
#include <string.h>
#include <stack>
 
#define mp make_pair
#define MOD 86400
#define INF 0x7fffffff
#define MAX_SIZE (int)1e5
 
using namespace std;
//ios::sync_with_stdio(false); cin.tie(0);
 
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<pii> vii;
typedef vector<pll> vll;
typedef vector<bool> vb;
 
int get_gcd(int a, int b) {
    return b ? get_gcd(b, a % b) : a;
}
 
int main() {
    int gcd, lcm;
    cin >> gcd >> lcm;
 
    int tmp = lcm / gcd;
 
    int left = 0, right = 0;
 
    for (int i = 1; i * i <= tmp; i++) {
        if (tmp % i == 0) {
            if (get_gcd(i, tmp / i) == 1) {
                left = i;
                right = tmp / i;
            }
        }
    }
 
    if (left > right) swap(left, right);
 
    cout << left * gcd << ' ' << right * gcd;
 
    return 0;
}