최대공약수와 최소공배수 : 문제 링크
- 두 수는 1이상 1000000이하의 자연수이다.
유클리드 호제법
- a, b가 정수이고 a >= b라고하고, a를 b로 나눈 나머지를 r이라고 한다. 이때 a와 b의 최대공약수를 (a, b)라고 하면 (a, b) = (b, r)이 성립한다.
#include <vector>
using namespace std;
int gcd(int a, int b) {
if(a % b == 0) return b;
else return gcd(b, a % b);
}
int lcm(int a, int b) {
return a * b / gcd(a, b);
}
vector<int> solution(int n, int m) {
vector<int> answer;
answer.push_back(gcd(n, m));
answer.push_back(lcm(n, m));
return answer;
}