Fraction
Time limit0.5sMemory limit1024 MB
Find the k-th smallest fraction in (0,1) whose denominator is at most M, and print it in lowest terms or -1 if it does not exist.
- Level
Medium7 of 10
- Topics
- Binary search, Number theory, Math, Sorting
- Solved
- No attempts yet
Problem
The JOI chairman M prayed to a photograph of a pyramid every day so that Japanese contestants would do well at IOI2008. One night a sphinx appeared in his dream and spoke.
Offer me a gold nugget, and I will grant your wish, but the nugget's weight must be less than 1 kg and must equal the k-th smallest fraction whose denominator is at most M. Lighter or heavier than this, the wish will not be granted.
M, who is very busy, told you, the national team candidates, to solve this problem.
Input
The input is a single line, containing the upper bound on the denominator M and the rank k of the fraction to find, separated by a space. M ≤ 30,000 and k ≤ 200,000.
Output
Write the output to standard output. The output is one line containing one or two integers. Write the numerator and denominator of the requested fraction in lowest terms, separated by a space. If no such fraction exists, write −1.
Hint
In the two examples above, the fractions with denominator at most 6, listed from smallest, are {1/6, 1/5, 1/4, 1/3, 2/5, 1/2, 3/5, 2/3, 3/4, 4/5, 5/6}, which is 11 fractions.