[백준] 2609번

https://www.acmicpc.net/problem/2609

최소공배수는 유클리드 호제법을 이용해서 구할 수 있다.

int gcd(int a, int b){
    int r = 1;
    while(r!= 0){
        r = a % b;
        a = b;
        b = r;
    }
    return a; 
}

a에는 최대공약수가 저장되어있다.

최소공배수는

최소공배수 구하는 법 : 수1 * 수2 / 최대공약수

로 구하면 된다.

이를 이용해서 문제를 풀면 된다.
(성공)

#include <bits/stdc++.h>
using namespace std;

int gcd(int a, int b){
    int r = 1;
    while(r!= 0){
        r = a % b;
        a = b;
        b = r;
    }
    return a; 
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);

    int n, m;
    cin >> n >> m;
    cout << gcd(n,m) << "\n" << n * m / gcd(n, m); 

    return 0;
}