[백준 3036] 링

문제 풀이

 

간단한 수학 문제다.

첫 번째 링을 한 바퀴 돌리면 그 링은 몇 바퀴 도는지 기약 분수 형태로 출력한다.

기약 분수 형태로 출력하고자 한다면 유클리드 호제법을 떠올리면 된다.

어떤 분수를 기약 분수 형태로 만들고 싶을 때 최대 공약수로 나누면 기약 분수 형태를 만들 수 있기 때문이다.

 

소스 코드

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int gcd(int a, int b)
{
	if (b == 0) return a;
	else return gcd(b, a % b);
}

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

	int n;
	cin >> n;
	vector<int> v(n);
	for (int i = 0; i < n; i++) cin >> v[i];
	for (int i = 1; i < n; i++)
	{
		int g = gcd(v[0], v[i]);
		int A = v[0] / g;
		int B = v[i] / g;
		cout << A << '/' << B << '\n';
	}
	return 0;
}