問題一覧 > 通常問題

No.2262 Fractions

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 29
作問者 : とりゐとりゐ / テスター : karinohitokarinohito sotanishysotanishy
2 ProblemId : 9330 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2023-04-07 22:21:52

問題文

あおばさんは,黒板に分母・分子がともに $N$ 以下の正整数である既約分数をすべて書きました.黒板に書かれた分数のうち,小さい方から $K$ 番目のものを求めてください.

ただし,黒板に書かれた既約分数が $K$ 個未満のときは -1 を出力してください.

$T$ 個のテストケースが与えられます.

入力

$T$
$\mathrm{case}_1$
$\vdots$
$\mathrm{case}_T$
各ケースは以下の形式で与えられます.
$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$
  • $1$ つの入力ファイルに含まれる $N$ の総和は $3\times 10^5$ 以下
  • 入力は全て整数

出力

$T$ 行出力してください.

$i$ 行目には,$i$ 番目のテストケースの答えを出力してください.黒板に書かれている分数が $K$ 個未満のとき -1 を,そうでないとき,求める分数を (分子)/(分母) の形式で出力してください.

サンプル

サンプル1
入力
5
2 1
2 2
2 3
2 4
200000 21871053595
出力
1/2
1/1
2/1
-1
2023/407

$N=2$ のとき,黒板には $3$ つの既約分数 $\dfrac{1}{2},\dfrac{1}{1},\dfrac{2}{1}$ が書かれています.$\dfrac{2}{2}$ は既約分数でないので書かれていません.

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。