BOJ 3036 : 링

#BOJ 3036 : 링

3036번: 링

#풀이

유클리드 호제법으로 풀 수 있다.

기약분수를 만드려면 분자,분모의 최대공약수를 구하여 나누면 기약분수를 만들 수 있다.

 

#코드

#include<iostream> //3include<bits/stdc++.h>
using namespace std;
int n;
int GCD(int a, int b) {
    if (b == 0)
        return a;
    return GCD(b, a % b);
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    int n, R;
    cin >> n >> R;

    while (--n) {
        int r;
        cin >> r;
        int g = GCD(R, r);
        cout << R / g << '/' << r / g << '\n';
    }
}