Level 1 최대공약수와 최소공배수

시간 복잡도: O(log(A+B))

1#include <bits/stdc++.h>
2using namespace std;
3
4// euclidean algorithm by division
5int gcd(int a, int b)
6{
7  if (a == 0) return b;
8  return gcd(b % a, a);
9}
10
11// least common multiple
12int lcm(int a, int b) {
13  return (a*b)/gcd(a, b);
14}
15
16vector<int> solution(int n, int m) {
17  vector<int> answer;
18  answer.push_back(gcd(n,m));
19  answer.push_back(lcm(n,m));
20  return answer;
21}

최대공약수(greatest common denominator)는 유클리드 호제법(Euclidean algorithm)을 사용했습니다.

1int gcd(int a, int b)
2{
3  if (a == 0) return b;
4  return gcd(b % a, a);
5}

최대공약수를 알면, 최소공배수(least common factor)도 바로 구할 수 있습니다.

1int lcm(int a, int b) {
2  return (a*b)/gcd(a, b);
3}