No.2262 Fractions
タグ : / 解いたユーザー数 29
作問者 :
とりゐ
/ テスター :
sotanishy
Problem Statement
Aoba wrote on a blackboard all irreducible fractions whose numerator and denominator are both positive integers at most $N$. Find the $K$-th smallest of the fractions written on the blackboard.
However, if fewer than $K$ irreducible fractions are written on the blackboard, output -1.
You are given $T$ test cases.
Input
$T$
$\mathrm{case}_1$
$\vdots$
$\mathrm{case}_T$
Each case is given in the following format.
$N\ K$
- $1\leq T\leq 1.5\times 10^4$
- $1\leq N\leq 3\times 10^5$
- $1\leq K\leq N^2$
- The sum of $N$ in $1$ input file is at most $3\times 10^5$
- All input values are integers
Output
Output $T$ lines.
On the $i$-th line, output the answer to the $i$-th test case. If fewer than $K$ fractions are written on the blackboard, output -1; otherwise, output the desired fraction in the format (分子)/(分母), that is, (numerator)/(denominator).
Sample
Sample 1
Input
5 2 1 2 2 2 3 2 4 200000 21871053595
Output
1/2 1/1 2/1 -1 2023/407
When $N=2$, the $3$ irreducible fractions $\dfrac{1}{2},\dfrac{1}{1},\dfrac{2}{1}$ are written on the blackboard. $\dfrac{2}{2}$ is not written because it is not irreducible.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。