問題一覧 > 通常問題

No.2262 Fractions

レベル : / AI推定難易度 : 2100 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 29
作問者 : とりゐ / テスター : karinohito sotanishy
お気に入りにしたユーザー ProblemId : 9330 / 自分の提出
問題文最終更新日: 2023-04-07 22:21:52
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 383 (順位表) の他の問題:

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もしくは右上の雲マークをクリックしてアカウントを作成してください。