분수 찾기
시간 제한2초메모리 제한128 MB
1<=p<q<=N인 기약분수들을 크기순으로 정렬했을 때 K번째 분수를 찾는 문제입니다.
문제
분모가 N 이하인 모든 기약분수 p/q를 값이 작은 순서대로 정렬한다. 각 분수는 1 <= p < q <= N을 만족해야 한다.
정렬된 목록에서 K번째 분수를 구하라.
입력
첫째 줄에 자연수 N과 K가 공백으로 구분되어 주어진다.
1 <= N <= 40,000이며, K는 분모가 N 이하인 기약분수의 전체 개수를 넘지 않는다.
출력
K번째 분수가 p/q라면 p와 q를 공백으로 구분해 출력한다. p와 q는 서로소여야 한다.