[Python] 백준 2436번(공약수) 문제 풀이

 

import math
a, apq = list(map(int, input().split()))
if a == apq:
    print(a, apq)
else:
    r = apq // a
    l = []
    for i in range(1, r//2+1):
        s = set([int(r/i), i])
        list_s = list(s)
        if int(r/i) > r/i or int(r/i) < r/i:
            continue
        if list_s in l:
            break
        if math.lcm(list_s[0]*a, list_s[1]*a) == apq and math.gcd(list_s[0]*a, list_s[1]*a) == a:
            l.append(list_s)
    answer = [l[-1][0]*a, l[-1][1]*a]
    print(min(answer), max(answer))

 

 잘 안 풀려서 구글 쳐봤는데 수학적으로 말해주는 곳이 없고 어떻게 풀어야 한다 절차만 알려줘서 그냥 내 방식대로 나 혼자 풀었다.

 

 우리가 구해야 하는 것은 입력받은 두 수를 최대공약수와 최소공배수로 하는 두 개의 자연수이다. 이 두 수를 n, m(단, n<m)이라고 하자. 그 두 수의 최대공약수를 a라 하자. 그렇다면 n=ap, m=aq(단, p,q∈N)로 나타낼 수 있다. 그러면 그 최소공배수는 apq가 될 것이다. 그러면 a가 주어지므로 pq의 값을 알 수 있다. 그러면 구한 pq를 만족시키는 모든 p와 q값을 구할 수 있다. 위 반복문에서는 그 모든 p와 q 값 중, a를 최대공약수로, apq를 최소공배수로 가지는 값을 [p,q] 혹은 [q,p]의 형태로 l이라는 리스트에 저장하였다. 그 중 두 자연수의 합이 최소가 되는 두 수를 구해야 하므로, p와 q의 합이 최소가 되는 두 수를 구해야 한다. 그 수는 l의 마지막 요소이다. 왜냐하면 i가 1부터 반복문이 돌아가기 때문이다. 그러니 리스트의 맨 마지막 요소를 가져와서, [p,q] 혹은 [q,p] 형태의 리스트를 [n,m] 혹은 [m,n]의 형태로 만들어 준다. n<m이므로, 작은 값이 n, 큰 값이 m이 되므로 "n m"의 형태로 출력할 수 있게 된다.

 

 그런데 희한하게 9번 라인에서 set()을 없애면 굉장히 편안할 것 같은데, set()을 없애면 실행 시간이 장난 아니게 길어진다. set()을 넣어야 빠르게 돌아간다. 이게 뭐지. 왜 그런지는 모르겠다.