728x90
반응형
문제출처:https://www.acmicpc.net/problem/1934
1934번: 최소공배수
두 자연수 A와 B에 대해서, A의 배수이면서 B의 배수인 자연수를 A와 B의 공배수라고 한다. 이런 공배수 중에서 가장 작은 수를 최소공배수라고 한다. 예를 들어, 6과 15의 공배수는 30, 60, 90등이 있
www.acmicpc.net
풀이:
import sys
input = sys.stdin.readline
# 유클리드
def gcd(x, y): #최대공약수 구하기
if y == 0:
return x
else:
return gcd(y, x%y)
def lcm(x, y): ## 최소공배수 구하기
result = (x*y) // gcd(x,y)
return result
num = int(input())
for i in range(num):
x, y = map(int, input().split(" "))
print(lcm(x, y))
반응형
댓글