[BOJ] 2436: 공약수 - python

이번에 푼 문제는 공약수이다.

배경지식

우선 이 문제를 풀기위해서 최대공약수와 최소공배수에 대한 기초 지식이 필요하다.

g = 최대공약수
l = 최소공배수

라고 했을 때 우리가 구해야 되는 수를 A,B라고 하면

A= a*g
B= b*g

라고 할 수 있다. 즉 A,B는 어떤 수에 g를 곱한 값이다.
예를 들어서 두 수의 최대공약수가 6이라면 당연히 두 수 모두 6을 약수로 가지고 있을 것이기 때문에 어떤 수에다가 최대공약수인 6을 곱한 수 일 수 밖에 없다.

그리고 또 하나의 중요한 식이 있는데

l = a * b * g (a,b는 서로소)

라는 것이다.

이건 그냥 개념만 알면 쉽게 이해할 수 있다.
60 과 48의 최소공배수를 구한다고 했을 때 아래처럼 구한다.

	2 ㅣ 60 48
    2 | 30 24
    3 | 15 12
      -------
        5  4
   
   => 최대공약수 : 2*2*3
   => 최소공배수 : 2*2*3*5*4
   (5,4는 서로소, 2*2*3은 최소공배수)

그러니까 최소공배수는 최대공약수에다가 서로소인 두 수를 곱한 값이 된다는 걸 알 수 있다.

최종 코드

import sys

input = sys.stdin.readline
from math import sqrt

min_sum = 200000000

g, l = map(int, input().split())

divide = l // g  # a*b = l/g

# 유클리드 호제법
def gcd(a, b):
    if a % b == 0:
        return b  # 최대공약수

    return gcd(b, a % b)


for a in range(1, int(sqrt(divide)) + 1):  # 1부터 divide의 제곱근까지 돌면서
    b = int(divide / a)  # b = (l/g)/a

    if divide % a == 0 and gcd(a, b) == 1:  # 약수고 서로소면
        if b - a < min_sum:  # 합이 최소면
            min_sum = b - a
            answer = f"{a*g} {b*g}"

print(answer)

난 이렇게 풀어서 통과를 했는데, 좀 더 빠르게 하고 싶으면 아래처럼 하면된다고 한다.

import sys

input = sys.stdin.readline
from math import sqrt

g, l = map(int, input().split())

divide = l // g  # a*b = l/g

# 유클리드 호제법
def gcd(a, b):
    if a % b == 0:
        return b  # 최대공약수

    return gcd(b, a % b)


for a in range(int(sqrt(divide)), 0, -1):  # 반대로 돌면서
    b = int(divide / a)  # b = (l/g)/a

    if divide % a == 0 and gcd(a, b) == 1:  # 약수고 서로소면
        print(a * g, b * g)
        break

sqrt(n)에 가까워질 수록 두 수의 합은 작아지기 때문에 반대로 돌면서 조건에 맞는 거 찾으면 출력하고 break하는 방법이다.

풀이과정

이제 위의 식을 이용하면 문제를 풀 수 있다

구해야 하는 것 : A, B
=> 우선 a,b를 구하고 각각에 g를 곱하면 됨
=> a,b를 구하자

a,b를 구하기 위해 사용할 수 있는 건 l,g
위 식에서 알 수 있는건 a*b = l/g
서로소인 a와 b를 곱하면 l/g가 되어야 함
=> l/g의 약수 중에 서로소이면서 곱해서 다시 l/g가 되는 두 수가 정답 후보군

서로소인 a,b를 구해야 함
=> 최대공약수가 1이면 됨
=> 유클리드 호제법 사용

합이 최소인 a,b를 구해야 함
=> 후보군 중에 합이 최소인 걸 출력

이런 흐름을 가지고 생각했다.

결론적으로 아래와 같은 프로그램을 짜면 된다

1. for문을 돌면서 a*b(즉 l/g)의 약수 두개를 뽑음
2. 서로소가 아니면 후보에서 탈락
3. 나온 후보들 중 두 값의 차이가 최소인 걸 찾아서 출력

알게 된 점

1. AB = L(A,B)G(A,B)이다
2. n의 약수를 찾을 때는 sqrt(n)까지만 찾으면 된다.
3. sqrt(n)에 가까워질 수록 두 수의 합은 작아진다.

2번의 이유

예를 들어서 12의 약수는 1,2,3,4,6,12 이다
1x12 = 12, 2x6 = 12 3x4=12 로 곱이 12로 일정하다.

약수의 개수를 c라고 하고 di를 n의 약수 중에서 i 번째 약수라고 한다면

n = dk * dc-k+1

가 성립한다.
즉, k번째 원소와 c-k+1번째 원소의 곱은 항상 n이다. (약수의 개수가 홀수인 경우는 짝지어지지 않는 값이 하나 생기는데, 이경우는 루트를 씌운 값이 약수가 됨 즉 sqrt(n)까지 보면 됨)

이렇게 어차피 약수는 짝을 지어 있기 때문에 sqrt(n)까지만 보면 된다.