[백준] 2436번 공약수

사용 언어 - Python3

문제 -  2436번 공약수

2436번: 공약수

 

정답

최대공약수 GCD(A,B), 최소공배수 LCM(A,B) (정답 맞춘 여부 X)

최대공약수 GCD(A,B)

1. GAP을 줄이기

공약수 = 일정한 간격으로 JUMP해서 A와 B 모두에 도달할 수 있는 수

GCD(12,8) = 0부터 8까지, 8부터 12까지 JUMP가 가능한 수 = GCD(8,12-8)

GCD(A,B) = GCD(B-A,A) = GCD(A-(B-A), B-A)

두 수이 최대공약수 = 간격을 최소로 줄여도 동일하다

 

2. 최대공약수 = 두 수 중 하나로 나누어서 나머지가 생기지가 않는다

12%8 = 4(나머지)

8%4 = 0(나머지 없음)

나머지 생기지 않으면, 두 수 중 작은 값이 최대공약수

 

3. 한 수를 가능한 만큼 갭을 줄인다.

하나의 수를 작은 수로 되는 만큼 뺀다 = 나누고 나서 나머지

121-7-7-7-7-7-.... = 121%7

7로 뺄수있을만큼 빼라 = 7로 나눈뒤에 나머지

 

 

최소공배수 LCM(A,B) = A*B // 최소공약수

 

 

최대공약수, 최소공배수의 범위는 두 값을 더한 값maxg보다는 무조건 작다.

gcd부터 루트 maxg까지 gcd만큼 jump 하면서 최대공약수를 찾는다.

_gcd(i,maxg//i) == gcd, _lcd(i,maxg//i) == lcm 를 만족하는

i와 maxg//i는 최소공배수, 최대공약수이다.

gcd,lcm = map(int,input().split())
maxg = gcd*lcm

# 최대공약수
def _gcd(a, b):
    while a % b != 0 : # 나머지가 0이 되는 순간 멈춘다 = 최대공약수 찾을 때까지 반복
        tmp = a % b
        a = b
        b = tmp
    return b # 작은 수

# 최소공배수
def _lcm(a,b):
    return a*b//gcd

answer = []

for i in range(gcd, int(maxg**0.5) + 1, gcd):
    if _gcd(i, (maxg//i)) == gcd:
        if _lcm(i, (maxg//i)) == lcm:
            answer.append((i,maxg//i))

print(*answer[-1])

 

python 모듈 활용하는 방법

import math

math.gcd()

 

 

레퍼런스

• 정답 깃허브

https://github.com/yyeongeun/codingtest/blob/main/BAEKJOON/2436_%EA%B3%B5%EC%95%BD%EC%88%98.py