Algorithm/백준 알고리즘_Python

[알고리즘][Python] 백준(BOJ) 5347 LCM_파이썬

알파이 2020. 10. 28. 15:36

 

5347 LCM    www.acmicpc.net/problem/5347

 

5347번: LCM

첫째 줄에 테스트 케이스의 개수 n이 주어진다. 다음 n개 줄에는 a와 b가 주어진다. a와 b사이에는 공백이 하나 이상 있다. 두 수는 백만보다 작거나 같은 자연수이다.

www.acmicpc.net

 

 

 

문제 풀기 전 공부할 것 : 수학, 정수론 유클리드 호제법

 

 

 

 

 

 

 

풀이

<내용>

  • a와 b의 최소 공배수를 구하는 방법은 a와 b를 곱하고 a와 b의 최대 공약수를 나누는 방법이 있다.
  • 따라서 최대 공약수를 구하는 gcd 함수를 정의한다.
    • 유클리드 호제법을 이용한다.
  • 그리고 최소 공배수를 구한다.

 

 

<코드>

import sys
input = sys.stdin.readline

def gcd(a, b):
    while b:
        mod = b
        b = a % b
        a = mod
    return a

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

 

 

 

 

 

 

 

 

728x90
반응형