[백준] 3036. 링

유클리드 호제법을 써서 최대공약수를 이용해서 풀었다.

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

 

#include <cstdio>


int GCD(int a, int b) {
    return a % b ? GCD(b, a%b) : b;
}

int main() {
    int n;
    scanf("%d", &n);
    int arr[102];
    for (int i = 0; i < n; i++) {
        scanf("%d", &arr[i]);
    }

    for (int i = 1; i < n; i++) {
        int gcd = GCD(arr[0], arr[i]);
        printf("%d/%d\n", arr[0]/gcd, arr[i]/gcd);
    }
}

 

나중에 찾아보니 유클리드 호제법은 이렇게 쓰는게 더 좋은것 같더라

int gcd(int a, int b)
{
	return b ? gcd(b, a%b) : a;
}