Algorithm in A..Z - 유클리드 호제법

개념

최대 공약수를 쉽게 구하는 방법

---

작동원리

ko.wikipedia.org/wiki/%EC%9C%A0%ED%81%B4%EB%A6%AC%EB%93%9C_%ED%98%B8%EC%A0%9C%EB%B2%95

유클리드 호제법 - 위키백과, 우리 모두의 백과사전

---

시간복잡도

O(1)

---

문제

www.acmicpc.net/problem/1934

1934번: 최소공배수

---

코드

#include <bits/stdc++.h>
using namespace std;

int gcd(int x, int y) {
    while (y) {
        int temp = x % y;
        x = y;
        y = temp;
    }

    return x;
}

int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);

    int t;
    cin >> t;
    while (t--) {
        int x, y;
        cin >> x >> y;
        cout << x * y / gcd(x, y) << "\n";
    }
}