백준 1934번[C] - 상세 풀이

https://www.acmicpc.net/problem/1934

1934번: 최소공배수

---

#include <stdio.h>

int T;

int gcd(int a, int b) {
    if(b == 0)
        return a;
    return gcd(b, a % b);
}

int main() {
    int x, y;
    
    scanf("%d", &T);
    
    for(int i = 0; i < T; i++) {
        scanf("%d %d", &x, &y);
        printf("%d\n", x * y / gcd(x, y));
    }
    
}

풀이 : 유클리드 호제법은 두 정수의 최대공약수(GCD)를 구하는 알고리즘으로

• 두 수 a와 b의 최대공약수는 b와 a % b의 최대공약수와 동일합니다.
• 이 작업은 b가 0이 될 때까지 반복됩니다. 이 때, a가 최대공약수가 됩니다.

즉, 최소공배수(LCM)를 유클리드 호제법을 사용하여 구하는 방법은 두 수의 곱을 최대공약수로 나눈 값입니다.