시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 47 6 5 26.316%

문제

분모가 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는 반드시 서로 소여야 한다.

예제 입력

5 6

예제 출력

3 5

힌트

출처

  • 문제를 번역한 사람: author5