[백준][C++] 3036: 링

문제

3036번: 링

풀이

유클리드 호제법

 

회전하는 바퀴는 반지름 / (첫 번째 링과 i 번째 링의 반지름의 gcd) 로 구할 수 있다. 

코드

#include <iostream>

using namespace std;

int nums[100];

int gcd(int a, int b)
{
    if (a < b)
    {
        swap(a, b);
    }

    int temp;
    while (b != 0)
    {
        temp = a % b;
        a = b;
        b = temp;
    }

    return a;
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);
    cout.tie(NULL);

    int N;
    cin >> N;

    for (int i = 0; i < N; ++i)
    {
        cin >> nums[i];
    }

    for (int i = 1; i < N; ++i)
    {
        int temp = gcd(nums[0], nums[i]);

        cout << nums[0] / temp << "/" << nums[i] / temp << '\n';
    }

    return 0;
}