분류 전체보기
-
boj 5347 - 최소공배수문제풀이/초급 2022. 6. 26. 23:42
boj.kr/5347 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 형으로는 오버플로우가..