Algorithm (알고리즘)
Algorithm in A..Z - 유클리드 호제법
강태종
2020. 12. 1. 00:15
개념
최대 공약수를 쉽게 구하는 방법
작동원리
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
유클리드 호제법 - 위키백과, 우리 모두의 백과사전
위키백과, 우리 모두의 백과사전. 유클리드 호제법(-互除法, Euclidean algorithm) 또는 유클리드 알고리즘은 2개의 자연수 또는 정식(整式)의 최대공약수를 구하는 알고리즘의 하나이다. 호제법이란
ko.wikipedia.org
시간복잡도
O(1)
문제
1934번: 최소공배수
두 자연수 A와 B에 대해서, A의 배수이면서 B의 배수인 자연수를 A와 B의 공배수라고 한다. 이런 공배수 중에서 가장 작은 수를 최소공배수라고 한다. 예를 들어, 6과 15의 공배수는 30, 60, 90등이 있
www.acmicpc.net
코드
#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";
}
}