[수학] [BJ1934] 최소공배수

코드 플러스

🚩 문제 설명

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

1934번: 최소공배수

BJ1934

⏱️ 시간 복잡도
▪ 최소공배수 LCM은 GCD를 구한다면 O(1)의 연산 시간으로 문제 해결 가능
▪ 최소공약수 GCD를 구하는 데 O(N)의 시간복잡도가 걸린다.

◾ 두 자연수의 최소공배수를 구하는 문제

 

 

 

---

 

 

 

✅ 입출력

1) 테스트 케이스 T가 주어진다.
2) 테스트 케이스의 수만큼 두 자연수 A, B가 주어진다.
return ➡️ 두 자연수 A, B가 주어졌을 때 두 수의 최소공배수를 출력

✔️ 예제 1

3
1 45000
6 10
13 17

45000
30
221

 

 

 

---

 

 

 

📑 문제 풀이

with 파이썬 (Python)

import sys
from math import gcd

T = int(sys.stdin.readline().strip())


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


for i in range(T):
    a, b = map(int, sys.stdin.readline().split())
    gcd_ = gcd(a, b)
    print(lcm(a, b, gcd_))

💬 Point

➡️  lcm = gcd * (a // gcd) * (b // gcd)
➡️  from math import gcd

◾ math 라이브러리를 활용하여 gcd를 구했다.

 

 

 

 

 

 

 

 

 

 

 

 

 

➕ 참고

https://yeomss.tistory.com/135

[수학] [BJ2609] 최대공약수와 최소공배수

 

# 코드 플러스 최소공배수 파이썬 python

# 백준 1934 최소공배수 파이썬 python

---