백준2436 공약수

작성일 | In

문제 링크

  • http://icpc.me/2436

문제 출처

  • 2011 KOI 초등부 2번, 중등부 1번, 고등부 1번

풀이

최대공약수를 $G$, 최소공배수를 $L$, 정답이 되는 두 수를 $A, B$라고 하면, 서로소인 두 자연수 $a, b$에 대해 $A = Ga, B = Gb, L = abG$라고 할 수 있습니다.

문제에서 $G, L$이 주어지므로 $ab = L/G$를 구할 수 있습니다. $ab$의 약수 $d$에 대해, $d$와 $ab/d$가 서로소라면 $d \cdot G$와 $(ab/g) \cdot G$는 정답이 될 수 있습니다.
정답이 될 수 있는 모든 후보를 구한 뒤, 두 수의 차가 가장 작은 것을 출력해주면 됩니다. 이때 $d$는 $\sqrt(ab)$까지만 봐도 충분합니다.

전체 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
/******************************
Author: jhnah917(Justice_Hui)
g++ -std=c++17 -DLOCAL
******************************/

#include <bits/stdc++.h>
#define x first
#define y second
#define all(v) v.begin(), v.end()
#define compress(v) sort(all(v)), v.erase(unique(all(v)), v.end())
#define IDX(v, x) (lower_bound(all(v), x) - v.begin())
using namespace std;

using uint = unsigned;
using ll = long long;
using ull = unsigned long long;

int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    int G, L; cin >> G >> L;
    int ab = L / G;

    int A = -1, B = -1; // A = Ga, B = Gb, L = abG
    for(int i=1; i*i<=ab; i++){
        if(ab % i == 0 && __gcd(i, ab/i) == 1) A = G*i, B = G*(ab/i);
    }
    cout << A << " " << B;
}