문제
두 자연수의 최소공배수(LCM)를 구하라.
입력
테스트 케이스 수 T와 각 케이스에 두 자연수 a, b가 주어진다.
출력
각 케이스마다 a와 b의 LCM을 출력한다.
예제
| 입력 | 출력 |
|---|---|
2 6 10 3 7 | 30 21 |
풀이
GCD를 이용한 LCM 공식으로 계산한다.
math.gcd(a, b)로 최대공약수를 구한다LCM = a * b / GCD(a, b)공식을 적용한다
핵심 아이디어: LCM(a, b) = a * b / GCD(a, b) 공식은 오버플로우를 방지하기 위해 a // gcd * b 순서로 계산하면 안전하다.
코드
import sys
import math
def main():
input = sys.stdin.read
data = input().strip().splitlines()
n = int(data[0])
results = []
for i in range(1, n + 1):
a, b = map(int, data[i].split())
lcm = a * b // math.gcd(a, b)
results.append(str(lcm))
print("\n".join(results))
if __name__ == "__main__":
main()복잡도
- 시간: O(T * log(min(a, b)))
- 공간: O(T)