[ 백준 ] 2436 / 공약수

金弘均·2021년 9월 15일
0

Baekjoon Online Judge

목록 보기
112/228
post-thumbnail

# Appreciation

/*
 * Problem :: 2436 / 공약수
 *
 * Kind :: Math
 *
 * Insight
 * - 최대공약수, 최소공배수 구하기
 *   + 6 | 30 36
 *       --------
 *          5  6  = 90
 *
 *     # 최대공약수 = G
 *       최소공배수 = L
 *       G | A B
 *         ------
 *           a b  = L (단, gcd(a,b) = 1)
 *
 *       -> A+B = G(a+b)
 *          min(A+B) => min(a+b)
 *          ab = L/G
 *
 *          => xy = ab 이고 gcd(x,y) = 1 인
 *             x,y 중 (x < y)
 *             y-x 가 최소인 x,y 를 찾아주자
 * 
 * - 그러한 x,y 를 어떻게 찾을까?
 *   + 30 의 약수 = 1, 2, 3, 5, 6, 10, 15, 30
 *     # 1+30 = 31
 *       2+15 = 17
 *       3+10 = 13
 *       5+6  = 11
 *       30 의 제곱근에 가까울수록 합이 작다
 *       -> ab 제곱근 이하의 가장 가까운 약수부터 검사해주자
 *          => x,y (x < y) 에서
 *             y 가 x 보다 더 크므로 x 의 감소율보다 y 의 증가율이 더 높기에
 *             x+y < x/2+2*y 이므로
 *             제곱근에 가까울수록 합이 작을 수밖에 없다
 *
 * Point
 * - int 로 하면 G 와 L 을 곱하면서 Overflow 가 일어날 수 있으므로
 *   넉넉하게 long 을 사용하자
 */

# Code

//
//  BOJ
//  ver.C++
//
//  Created by GGlifer
//
//  Open Source

#include <iostream>
#include <cmath>
#include <numeric>

using namespace std;

#define endl '\n'

// Set up : Global Variables
/* None */

// Set up : Functions Declaration
/* None */


int main()
{
    // Set up : I/O
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    // Set up : Input
    long G, L;
    cin >> G >> L;

    // Process
    long ab = L/G;
    long A, B;
    for (long i=sqrt(ab); i>=1; i--) { /* x=i,  y=ab/i */
        /* i=1 이면 아래 if 문의 조건식이 참이 될 수밖에 없음
         * 따라서, 어떤 G,L 이 주어지더라도 if 문이 실행되어 A,B 를 구할 수 있음 */
        if (ab % i == 0 && gcd(i, ab/i) == 1) { 
            A = i * G;
            B = ab / i * G;
            break;
        }
    }

    // Control : Output
    cout << A << ' ' << B << endl;
}

// Helper Functions
/* None */
profile
이런 미친 게임을 봤나! - 옥냥이

0개의 댓글