[백준 1934]알고리즘 57일차 : 최소공배수

www.acmicpc.net/problem/1934

1934번: 최소공배수

C++ 정수론 및 조합론

양아치 같지만 정수론 및 조합론에 문제가 추가돼있어서..

공유기설치하다가 넘어왔습니다..

 

접근방법

유클리드 호제법으로 풀이한 최소공배수

- 유클리드 호제법 : A에는 B를 대입하고, B에는 A%B를 대입하면서 A%B가 0이 될때 B의 값이 최대공약수이다.

- 최소 공배수 = 두수의 곱 / 최대공약수

이 두가지를 적용해서 푼 코드

 

소스코드

#include <iostream>
using namespace std;

int main(){
    int T;
    cin >> T;
    int A,B,temp,result;
    
    for(int i = 0 ; i < T ; i++){
        cin >> A >> B;
        result = A*B;
        while(A%B != 0){
            temp = B;
            B = A%B;
            A = temp;
        }
        cout << result/B << "\n";
    }
    return 0;
}