시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 128 MB9216833.333%

문제

분모가 N 이하인 모든 기약분수 p/q 를 증가하는 순서대로 나열하려고 한다. (1 ≤ p < q ≤ N) 예를 들어 N=5인 경우, 아래와 같이 나열할 수 있다.

1/5, 1/4, 1/3, 2/5, 1/2, 3/5, 2/3, 3/4, 4/5

N이 주어졌을 때, 위와 같이 분수를 나열했을 때 K번째 분수를 구하는 프로그램을 작성하시오. 예를 들어 N=5이고 K=6인 경우 구하고자 하는 분수는 3/5가 된다.

입력

첫째 줄에 자연수 N과 K가 빈 칸을 사이에 두고 주어진다. (1 ≤ N ≤ 40,000) 분모가 N 이하인 모든 기약분수의 개수보다 K가 큰 경우는 없다.

출력

첫째 줄에 K번째 분수가 p/q인 경우 p와 q를 빈 칸을 사이에 두고 출력한다. p와 q는 반드시 서로소여야 한다.

예제 입력 1

5 6

예제 출력 1

3 5

출처

  • 문제를 번역한 사람: author5