[백준(BOJ)] #2436- 공약수 (파이썬, PyPy3)

문제

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

2436번: 공약수

 

---

문제 풀이

최대공약수와 최소공배수의 성질을 이용해 풀이

2022.07.01 - [PS/프로그래머스] - [프로그래머스(Programmers)/ Level2] N개의 최소공배수 (파이썬, Python3)

[프로그래머스(Programmers)/ Level2] N개의 최소공배수 (파이썬, Python3)

 

구하고자 하는 자연수 x, y에 대해 두 자연수는 각각
x = x' * GCD
y = y' * GCD
로 표현될 수 있음

GCD는 x, y의 제일 큰 공약수이므로 x'와 y'는 서로소(더이상 공통된 약수가 없음)

LCM / GCD = (x * y / GCD ) / GCD = (x' * y' * GCD^2 / GCD) / GCD = x' * y'

두 자연수의 합이 최소가 되는 경우를 구해야 하기 때문에 산술 기하평균 공식에 의해 x' * y'의 제곱근과 가까울수록 두 자연수의 합이 최소가 됨

x' * y' 의 제곱근부터 1까지 임의의 자연수 a를 x'에 대입하고, LCM / GCD = x' * y'의 성질을 이용하여 y'를 구함

이때 x', y'는 서로소여야 하므로 서로소인 x', y'만 후보가 됨

 

---

구현

코드

import sys
import math
input = sys.stdin.readline


def get_gcd(a, b):
    p = a % b
    if p == 0:
        return b
    else:
        return get_gcd(b, p)


if __name__ == "__main__":
    gcd, lcm = map(int, input().split())
    div = lcm // gcd  # a * b

    for a in range(int(math.sqrt(div)), 0, -1):
        b = div // a

        if div % a == 0 and get_gcd(a, b) == 1:
            print(a * gcd, b * gcd)
            break

 

결과