알고리즘16 :: BOJ_13241

단순히 최소공배수를 구하는 문제였다.

다만, 두 수가 서로소 일경우는 if(b==1)이 없이는 무한루프가 돌 수 있기 때문에 b==1 이란 블락을 하나 생성하여 추가해줬다.

최소 공배수는 알다싶이, (a*b)%gcd 로 계산할 수 있다.

주의할 점은 문제에서 언급한대로 값이 크기 때문에 long long int를 사용해야 했었다.

(...처음에 서로소를 찾는 문제인줄 알고 에라토스 테네스 체를 구현하고 있었는데, 다시 보니까 전혀 아니더라카더라)

#include<bits/stdc++.h>

using namespace std;

const int MAX = 1000000;

int prime[MAX];

int pn;

bool check[MAX+1];

int gcd(int a, int b){

    if(b==0)

        return a;

    if(b==1)

        return 1;

    gcd(b, a%b);

}

int main(){

    ios_base::sync_with_stdio(false);

    cin.tie(nullptr);

    long long int a,b;

    cin>>a>>b;

    int _gcd = gcd(a,b);

    cout<<(a*b)/_gcd<<endl;

}

내 블로그 - 관리자 홈 전환	`Q` `Q`
새 글 쓰기	`W` `W`

글 수정 (권한 있는 경우)	`E` `E`
댓글 영역으로 이동	`C` `C`

알고리즘16 :: BOJ_13241_최소공배수