P8058 [BalkanOI 2003] Farey Sequence

Arrange all **reduced proper fractions** whose numerator and denominator are both $\leq n$ in increasing order. The resulting sequence is called the Farey sequence. Find the $k$-th smallest number in the Farey sequence for the given $n$.

One line with two integers $n, k$.

One line with two integers $p, q$, representing the answer $\frac{p}{q}$.

For $100\%$ of the testdata, $2 \leq n \leq 4 \times 10^4$, and $1 \leq k \leq$ the number of fractions that satisfy the conditions. Translated by ChatGPT 5