백준 3036번 링[C++]

3036번은 유클리드 호제법을 사용하여 풀이하면 쉽게 풀 수 있습니다.

#include <iostream>
#include <vector>

using namespace std;

int n, tmp;
vector<int> v;

int gcd(int x, int y){
    int a, b, c = -1;
    a = x;
    b = y;
    while(1){
        c = a % b;
        if(a % b == 0)
            break;
        a = b;
        b = c;
    }
    return b;
}
int main(){
    scanf("%d", &n);
    for(int i = 0; i < n; i++){
        scanf("%d", &tmp);
        v.push_back(tmp);
    }
    for(int i = 1; i < n; i++){
        int r;
        if(v[0] >= v[i])
            r = gcd(v[0], v[i]);
        else
            r = gcd(v[i], v[0]);
        printf("%d/%d\n", v[0] / r, v[i] / r);
    }
}