[BOJ/백준/C++] 1934번 최소공배수

1934번: 최소공배수

---

반응형

📌 접근 방법

⚡ 최소 공배수 구하는 공식

int LCM(int a, int b){
    return a*b/GCD(a,b);
}

• a * b / 최대 공약수를 이용하면 구할 수 있음

 

⚡ 최대 공약수 구하는 공식

int GCD(int a, int b){
    int c = a%b;
    while(c!=0){
        a=b; 
        b=c;
        c=a%b;
    }
    return b;
}

• 유클리드 호제법을 이용해서 구함
  • 유클리드 호제법 : 두 정수 a, b에 대해, a를 b로 나눈 나머지인 c을 이용해서 최종적인 나머지가 0이 될 때까지 위의 과정을 반복하는 것

 

✔ 유클리드 호제법

• 최대 공약수를 구하는 알고리즘
• 두 정수 a, b에 대해, a(더 큰 수)를 b(더 작은 수)로 나눠서 나머지를 구한다.
• 나머지인 r을 이용해서 최종적인 나머지가 0이 될 때까지 위의 과정을 반복한다.
• 나머지가 0이 됐을 때 마지막 계산에서 나누는 수로 이용된 수가 최대 공약수가 된다.

 

 

✅  Pass Code

#include<iostream>
#include<string>
#include<cmath>
#include<algorithm>
#include<vector>
#include<iterator>
#include<map>
#include<set>
using namespace std;
int GCD(int a, int b){
    int c = a%b;
    while(c!=0){
        a=b; 
        b=c;
        c=a%b;
    }
    return b;
}
int LCM(int a, int b){
    return a*b/GCD(a,b);
}
int main() {

    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int T,A,B;
    cin>>T;
    for(int i=0; i<T; i++){
        cin>>A>>B;
        cout<<LCM(A,B)<<'\n';
    }

    return 0;
}