boj 5347 - 최소공배수

문제풀이/초급

씨플라스 2022. 6. 26. 23:42

5347번: LCM

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

www.acmicpc.net

문제 설명

데이터 케이스 수 n이 주어지고,

a,b가 주어지는데 a와 b의 최소 공배수를 구하는 문제이다.

먼저 간단한 풀이이다. a와 b의 최대 공약수를 gcd이라고 보자.

그렇다면 a=A*gcd,b=B*gcd꼴로 나타낼 수 있다.

(단 A,B는 서로소여야한다)

ㄴgcd가 최대공약수니 자명하게 서로소다.

a와 b의 최대공약수는 a*b/gcd

코드는 위 내용처럼 a와 b를 받고 a*b/gcd를 하면 되는 것이다.

a와 b가 백만임으로 int 형으로는 오버플로우가 발생한다.

그러므로 더 큰 자료형인 long long int 를 사용하였다.

최대 공약수를 빠르게 구하는 법을 모른다면 다음 글을 보도록하자.