백준 1934 - 최소공배수[유클리드 호제법]

https://www.acmicpc.net/problem/1934

1934번: 최소공배수

최소 공배수 = 두 수의 곱 나누기 최대 공약수

 

 

최대 공약수 구하는 법 [유클리드 호제법]

n=int(input())

for _ in range(n):
    a,b=map(int,input().split())
    tmp=a*b

    while b != 0:
        r = a % b
        a = b  
        b = r
        
    print(a) # 최대공약수

 

 

 

 즉, a,b는 한번의 연산마다 하나는 나머지로, 다른 하나는 다른 값으로 갱신 시켜 주면 된다.

또한 a,b의 대소 관계 상관없이 아래 코드를 사용할 수 있다.

그후 최종적으로 초기 두값의 곱 나누기 최대공약수를 하면 최소공배수를 구할 수 있다.

n=int(input())

for _ in range(n):
    a,b=map(int,input().split())
    tmp=a*b

    while b != 0:
        r = a % b
        a = b  
        b = r
    print(tmp//a)

 

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

def lcd(a, b):
    return a * b // gcd(a, b)

t = int(sys.stdin.readline().rstrip())
for _ in range(t):
    a, b = map(int, sys.stdin.readline().rstrip().split())
    print(lcd(a, b))

 

 

 

 

참조

https://www.youtube.com/watch?v=TxdljAFjTNw