boj 5347 - 최소공배수

boj.kr/5347

5347번: LCM

문제 설명 

데이터 케이스 수 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 를 사용하였다.

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

boj 2609 - 최대공약수와 최소공배수 :: Standard Template Library (tistory.com)