[백준 3036] 링

문제 링크 : https://www.acmicpc.net/problem/3036

3036번: 링

사용 알고리즘 :

GCD

 

서로 다른 톱니바퀴 A와 B가 맞물려 있을 때

 

A가 n톱니만큼 돌아가면 B도 n톱니 만큼 돌아가는 것은 당연한 사실이다.

 

A가 a개 만큼의 톱니를 가지고 있고 B가 b개 만큼의 톱니를 가지고 있다고 한다면

 

A가 한바퀴 회전했을 때(a톱니 만큼 돌아갔을 때) B는 a/b 바퀴 만큼(a톱니 만큼) 돌아간다.

 

---

 

다음으로 구해진 모든 분수를 기약분수로 나타내면 된다.

 

이는 GCD알고리즘을 사용하여 빠르게 해결할 수 있다.

 

---

 

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

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

int main(void) {
	int n;
	cin >> n;

	int fst;
	cin >> fst;
	for (int i = 1; i < n; i++) {
		int a;
		cin >> a;
		int tmp = gcd(fst, a);
		cout << fst / tmp << "/" << a / tmp << endl;
	}

	return 0;
}