問題一覧 > 通常問題

No.2266 Fractions (hard)

レベル : / 実行時間制限 : 1ケース 6.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 8
作問者 : とりゐとりゐ / テスター : sotanishysotanishy
0 ProblemId : 9488 / 自分の提出
問題文最終更新日: 2023-04-08 12:41:13

問題文

Fractions の制約強化バージョンです．

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

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

入力

$N$ $K$

  • $1\leq N\leq 10^8$
  • $1\leq K\leq N^2$
  • 入力は全て整数

出力

黒板に書かれている分数が $K$ 個未満のとき -1 を，そうでないとき，求める分数を (分子)/(分母) の形式で出力してください．

サンプル

サンプル1
入力
200000 21871053595
出力
2023/407
サンプル2
入力
100000000 100000000000000
出力
2922326/88828059
サンプル3
入力
100000000 6079271032731815
出力
100000000/1

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