합동 공격
면접 대비시간 제한1초메모리 제한512 MB
계수로 주어진 연분수를 기약분수 하나로 계산해 출력한다. 분자와 분모는 모두 10^18 미만이다.
문제
토르스타인 장군이 다음 합동 공격의 x좌표를 보냈으니, 파멸을 막기 위해 그의 명령에 즉시 따라야 한다. 안타깝게도 토르스타인은 두 자리를 넘는 숫자를 싫어하고 가로 선분을 좋아해서, 좌표를 연분수로 보냈다. 즉
[ x=x_0+\frac{1}{x_1+\frac{1}{\ldots}} ]
토르스타인은 좌표를 기약분수로만 받는 로켓 발사기를 가지고 있으므로, 공격을 시작하기 위해 발사기에 넣을 올바른 숫자를 재빨리 계산해야 한다. 서둘러라! 실패하면 끔찍한 결과가 따른다!
입력
첫 줄에 연분수의 계수 개수인 정수 n (1 ≤ n < 40)이 주어지고, 다음 줄에 x의 계수인 n개의 정수 (1 ≤ xi < 100)가 주어진다.
출력
좌표 x를 기약분수로 출력한다. 분자와 분모는 모두 1018보다 작음이 보장된다.