No.2262 Fractions
レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限
: 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 29
作問者 : とりゐ / テスター : karinohito sotanishy
タグ : / 解いたユーザー数 29
作問者 : とりゐ / テスター : karinohito sotanishy
問題文最終更新日: 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もしくは右上の雲マークをクリックしてアカウントを作成してください。