유클리드 호제법

June 8, 2018 - 1 minute read -
알고리즘

A > B 일 때, A를 B로 나눈 나머지를 r이라고 한다면, A, B의 최대 공약수 = B,r의 최대 공약수가 성립한다.

백준 1934번

testCase = int(input())

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

while testCase > 0:
    testCase -= 1
    
    num1, num2 = map(int, input().split())

    if num1 > num2:
    num1, num2 = num2, num1

    print(int(num1 * num2 / gcd(num1, num2)))

Resource

https://www.acmicpc.net/problem/1934
https://www.youtube.com/watch?v=J5Yl2kHPAY4