[Level 1, C++] 최대공약수와 최소공배수

문제 : 최대공약수와 최소공배수

---

풀이 방법

유클리드 호제법을 쓰지 않으면 시간 오류가 뜨기 때문에 유클리드 호제법을 찾아봐야한다.

공식을 이해하느라 유튜브도 찾아보고 그랬었긴 했다.

 

 

원리를 설명하는 영상은 이 영상이 최고인듯하다.

---

풀이 코드

#include <string>
#include <vector>
using namespace std;

vector<int> solution(int n, int m) {
    vector<int> answer(2, 1);
    int a, b, tmp;
    
    if(n > m)
    {
        
        tmp = m;
        m = n;
        n = tmp;
    }
    
    a = n, b = m, tmp = 0;
    
    while(b % a != 0)
    {
        tmp = b % a;
        b = a;
        a = tmp;
    }
    
    answer[0] = a;
    answer[1] = (n * m) / answer[0];
    
    return answer;
}