[BOJ S5][C++] 백준 14490번: 백대열

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

14490번: 백대열

 

문제

대열이는 욱제의 친구다.

• “야 백대열을 약분하면 뭔지 알아?”
• “??”
• “십대일이야~ 하하!”

n:m이 주어진다. 욱제를 도와주자. (...)

입력

n과 m이 :을 사이에 두고 주어진다. (1 ≤ n, m ≤ 100,000,000)

출력

두 수를 최대한으로 약분하여 출력한다.

 

풀이

유클리드 호제법을 이용한다

[🌲 Altu-Bitu/0913 정수론] - [BOJ][C++] 백준 2609번 : 최대공약수와 최소공배수

// Authored by : seondal
// Co-authored by : -

// #include <bits/stdc++.h>
#include <iostream>
#include <stdio.h>

using namespace std;

int getGcd(int n, int m) {
    if(m == 0) return n;
    return getGcd(m, n%m);
}

int main() {
    int n, m;
    scanf("%d:%d", &n, &m);
    
    int gcd = getGcd(n, m);
    
    cout << n/gcd << ":" << m/gcd;
    
    return 0;
}

/*
 */