백준 2436 공약수

2011 정보올림피아드 초등부 2번 문제이다.

문제 풀이

 주어진 두 수를 a, b, 두 수의 최대공약수를 g, 최소공배수를 l이라 하면, a, b, g, l의 관계는 다음과 같다.

 $A = \frac{a}{g}$

 $B = \frac{b}{g}$

 $l = g \times A \times B$

 위의 관계를 이용하면 $B$는 다음과 같이 쓸 수 있다.

 $B = \frac{l}{g \times A}$

 따라서, 가능한 A에 대하여 B를 구하고 A와 B가 서로소인지 확인하면 된다.

Python Code

import sys, math
def gcd(a, b):
  while (b != 0):
    temp = a % b
    a = b
    b = temp
  return abs(a)
def solution(g,l):
    ans = (l,l)
    temp = (0,0)
    for A in range(math.ceil(math.sqrt(l//g)),0,-1):
      if l%(g*A) == 0:
        B = l//(g*A)
        temp = (A*g,B*g)
        if gcd(A,B) == 1 and sum(temp) < sum(ans):
          ans = temp
                
    print(min(ans),max(ans))
if __name__ == "__main__":
    g,l = map(int,sys.stdin.readline().split())
    solution(g,l)

Line 11 : 가능한 A에 대하여

Line 13 : B를 구하고

Line 15 : A와 B가 서로소인지 확인한다.

 

For 문 (가능한 A)의 범위에 대하여

 첫번째 풀이에서는 for문을 아래와 같이 작성하였고, 3784 ms가 걸렸다. 통과 후, 다른 사람들의 기록을 보니 52ms로 약 60배가 빨라서 뭔가 확인해보니 for문의 범위가 문제였다.

 아래의 풀이의 경우에는 A를 1부터 l//g 까지 모든 A, B 쌍에 대하여 계산하였는데, 위의 a, b, g, l의 관계를 이용하면 A와 B가 같을 때, 즉 $A^2 = \frac{l}{g}$ 인 경우가 산술기하평균으로부터 합이 가장 작은 A, B 쌍인 것을 알 수 있으므로, A를 $\sqrt{\frac{l}{g}}$ 부터 1씩 내리며 만족하는 A와 B를 찾으면 바로 리턴하는 것이 최적해 임을 알 수 있다. 위의 풀이의 경우 60 ms가 걸렸다.

def solution(g,l):
    ans = (l,l)
    for A in range(1,l//g+1):
        if l%(A*g) == 0:
            a = A*g
            B = l//(A*g)
            b = B*g
            if gcd(A,B) == 1 and a+b < sum(ans):
                ans = (a,b)

문제 링크

2436번: 공약수