알고리즘/BAEKJOON
BOJ 2609 : 최대공약수와 최소공배수
피로물든딸기
2021. 5. 5. 13:52
반응형
두 수 A, B의 최대공약수가 G라면 A = a * G, B = b * G로 정의할 수 있다.
그러면 최소공배수는 a * b * G = A * B / G 가 된다.
최대공약수는 유클리드 호제법으로 구할 수 있다.
A % B = R이라고 하면, A와 B의 최대공약수는 B와 R의 최대공약수와 같다. (A ≥ B)
즉, B가 0이 아닌 경우 gcd(B, A % B)를 구한다.
이 과정을 B가 0이 되는 경우에 A를 return하면 된다.
최소공배수의 경우 A * B / G의 경우 A * B 연산에 의해 overflow가 발생할 수 있다.
따라서 나누기를 먼저해서 (A / G * B) overflow를 방지한다.
#include <stdio.h>
int gcd(int a, int b)
{
return (b) ? gcd(b, a % b) : a;
}
int lcm(int a, int b)
{
return a / gcd(a, b) * b;
}
int main(void)
{
int a, b;
scanf("%d %d", &a, &b);
printf("%d\n", gcd(a, b));
printf("%d\n", lcm(a, b));
return 0;
}
반응형