[3036] 링

---

첫번째 링이 한 바퀴 돌 때 나머지 링은 몇 바퀴 도는지 출력해야 한다

원리는 쉽다

 

첫번째 링의 둘레와 해당하는 링의 둘레를 서로 나누면 되는데, 반지름 * 2 한 것을 나눠서 기약 분수로 만드나, 반지름을 나눠서 기약 분수로 만드나 값은 똑같으므로 반지름만으로 구해도 된다

 

근데 기약분수로 바꾸는게 좀 어려웠다

C++에서 '/'는 나머지없이 몫만 출력하기 때문에 다른 방법을 생각해야했다

 

결론적으로 분모와 분자의 최대공약수를 구한 다음 각각 분모, 분자에 대해 최대공약수로 나누면 기약분수 형태가 나왔다

최대공약수 구하는 방법은 유클리드 호제법을 이용하였다

유클리드 호제법을 이용할 때는 작은 수가 앞에 와야한다

#include <iostream>
using  namespace std;

int N;
int F, Nx;

int gcd(int a, int b) { // 유클리드 호제법
	int c;
	while (b != 0) {
		c = a % b;
		a = b; b = c;
	}

	return a;
}

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

	cin >> N;

	cin >> F;
	for (int i = 0; i < N-1; i++)
	{
		cin >> Nx;
		// (제일 첫번째 링 / 최대 공약수) / (해당하는 링 / 최대 공약수)
		int d = gcd(Nx, F); // 작은 것부터 넣어줌
		printf("%d/%d\n", F / d, Nx / d);
	}
}