| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 0.5 초 | 1024 MB | 1837 | 373 | 221 | 18.954% |
이상하게 들릴지 모르지만, 재훈은 요즘 0ドル$과 1ドル$사이의 기약 분수(irreducible fraction)를 오름차순으로 나열하는 것에 관심이 많다. 이를 위해, $n$차 수열 $R(n)$을 0ドル$과 1ドル$사이의 기약 분수중에서 분모가 $n$ 이하인 기약 분수의 오름차순 수열로 정의하고, 이를 Reafy 수열이라고 부르기로 했다. 여기서, $n$은 양의 정수이다.
예를 들어, 1ドル$차부터 5ドル$차까지의 Reafy 수열은 다음과 같다.
$$R(1) = \left\{ \frac{0}{1}, \frac{1}{1} \right\}$$
$$R(2) = \left\{ \frac{0}{1}, \frac{1}{2}, \frac{1}{1} \right\}$$
$$R(3) = \left\{ \frac{0}{1}, \frac{1}{3}, \frac{1}{2}, \frac{2}{3}, \frac{1}{1} \right\}$$
$$R(4) = \left\{ \frac{0}{1}, \frac{1}{4}, \frac{1}{3}, \frac{1}{2}, \frac{2}{3}, \frac{3}{4}, \frac{1}{1} \right\}$$
$$R(5) = \left\{ \frac{0}{1}, \frac{1}{5}, \frac{1}{4}, \frac{1}{3}, \frac{2}{5}, \frac{1}{2}, \frac{3}{5}, \frac{2}{3}, \frac{3}{4}, \frac{4}{5}, \frac{1}{1} \right\}$$
두 양의 정수 $n$과 $k$가 입력으로 주어지면 Reafy 수열 $R(n)$의 $k$번째 기약 분수를 출력하는 프로그램을 작성하시오. $R(n)$의 첫 번째 기약 분수는 $\frac{0}{1}$이고 $|R(n)|$-번째 기약 분수는 $\frac{1}{1}$이다.
입력은 표준입력을 사용한다. 첫 번째 줄에 두 양의 정수 $n$과 $k$가 주어진다. 두 정수의 범위는 1ドル ≤ n ≤ 5,000円,ドル 1ドル ≤ k ≤ |R(n)|$이다.
출력은 표준출력을 사용한다. $R(n)$의 $k$-번째 기약 분수가 $\frac{a}{b}$라면 $a$와 $b$값을 차례대로 공백 하나를 사이에 두고 출력한다.
4 3
1 3
5 9
3 4