제목 그대로 구하면 되는 문제이다.
유클리드 호제법이라는 최대공약수를 구하는 알고리즘도 존재한다.
#include <string>
#include <vector>
#include <unordered_map>
#include <cmath>
using namespace std;
void getElements(int num, unordered_map<int, int>& um) {// 공약수를 구해준다.
while (num > 1) {
for (int i=2; i<=num; i++) {
if (num%i == 0) {
um[i]++;
num /= i;
break ;
}
}
}
}
vector<int> solution(int n, int m) {
vector<int> answer(2, 1);
unordered_map<int, int> um_n, um_m;
getElements(n, um_n);
getElements(m, um_m);
for (auto c : um_n) {
if (um_m[c.first]) {
answer[0] *= c.second > um_m[c.first] ? pow(c.first, um_m[c.first]) : pow(c.first, c.second);
}
um_m[c.first] = c.second > um_m[c.first] ? c.second : um_m[c.first];
}
for (auto c : um_m) {
answer[1] *= pow(c.first, c.second);
}
return answer;
}
#include <string>
#include <vector>
using namespace std;
int gcd(int a, int b) {// 최대 공약수
return (b ? gcd(b, a%b) : a);
}
int lcm(int a, int b) {// 최소 공배수
return (a*b / gcd(a, b));
}
vector<int> solution(int n, int m) {
return {gcd(n, m), lcm(n, m)};
}