lcm

문제 설명세 정수 a, b, L이 주어졌을 때, LCM(a, b, c) = L을 만족하는 가장 작은 c를 찾는 프로그램을 작성하시오. LCM(a, b, c)는 a, b, c의 최소공배수이다.https://www.acmicpc.net/problem/11688       제한 사항      풀이문제를 요약하면, a, b, L이 주어졌을 때, a, b, c의 최소공배수가 L이 되도록 하는 c의 최솟값을 구해야 한다. 우선, 해당 문제를 풀기 위해서는 gcd(최대공약수)와 lcm(최소공배수)을 구하는 방법을 알아야 한다.gcd는 다음과 같은 간단한 함수로 구할 수 있다.long long gcd(long long y, long long x){ if (x == 0) return y; return gcd(..

최대공약수와 최소공배수를 구하는 문제이다. 선형적인 탐색법으로 작은 수전까지 하나씩 나누어 보고 둘 다 나누어 떨어지는 수 중 가장 큰 수를 구하면 되겠지만, 다른 수학적인 방법을 이용하여 최대공약수를 구한 뒤 그를 이용하여 최소 공배수까지 구하는 방법이 있다. 임의의 수 a, b가 있다 가정하자. (단, a > b) a를 b로 나누면 몫과 나머지가 있을 것이다. 그러면 그 나머지로 나누는 수 (b)를 또 나눈다. 이를 반복하다 나누는 수 (b)가 0이 되면 나누어지는 수 a를 return 한다. 그림을 보면 x가 최대공약수라 할 때, a = 8x b = 3x a% b = 2x이다. 우리는 x를 구해야 하기 때문에, 나머지가 0이 될 때, 즉 모든 수가 나누어 떨어질 때까지 계속해서 b를 나머지로 나눈다..