거스름돈이 싫어요
면접 대비시간 제한1초메모리 제한512 MB
N개의 분수가 주어질 때, 모든 분수를 나누어떨어지게 하는 가장 큰 분수를 구해 기약분수로 출력한다.
문제
프로불편러 지수는 딱 떨어지지 않는 수를 싫어한다. 거스름돈이 남는 것도 싫어한다. 지수가 아이템을 사려고 하는데, 아이템의 가격은 모두 분수로 되어 있다. 예를 들어 3/2코인짜리 아이템을 사려고 2코인을 적립해 결제하면 1/2코인이 남는다. 그래서 지수는 개발사에 모든 아이템을 딱 떨어지게 나눌 수 있는 가격 단위를 건의하려고 한다. 새로운 가격 단위는 최대 몇 코인인지 구하라.
N가지 종류의 아이템을 딱 떨어지게 나눌 수 있는 코인 단위를 구하라. 이때 아이템과 코인은 모두 분수 형태로 나타내야 한다.
입력
첫 번째 줄에는 아이템의 개수 N (1 ≤ N ≤ 50)이 주어진다.
두 번째 줄부터는 한 줄에 분자 A, 분모 B (1 ≤ A, B ≤ 40) 쌍이 주어진다. 이는 기약분수 형태가 아닐 수도 있다.
출력
새로운 코인 단위의 분자, 분모를 공백으로 구분하여 출력한다. 단, 기약분수 형태이다.