(難易度目安 : 点)
自然数が与えられた時、以上 以下であり、分母が以下であるような規約分数を小さい順に並べた結果得られる数列をと定義します。
例えば、
=
=
です。
自然数が与えられます。
以下の個のクエリに解答してください。
◎自然数と互いに素な自然数のペアが与えられる。
分数はの要素かつその番目の項であるとする。
の番目の要素をと表すとき、自然数のペアを求めよ。
・テストケースは個与えられる。
・
◉全てのテストケースに対して以下が成り立つ。
・入力はすべて正の自然数
・
・かつはの要素である
はじめに = (テストケースの数)が与えられる。
その後回にわたって,番目のクエリが与えられる。
各クエリは以下の形式で与えられる。
M p q
テストケース全体での入力は以下で与えられる。
T M_1 p_1 q_1 M_2 p_2 q_2 . . . M_T p_T q_T
全部で行出力してください。
行目には、番目のクエリの自然数のペアを出力してください。
最後に改行してください。
4 2 1 2 6 4 5 7 2 3 6 3 5
1 1 5 6 5 7 2 3
つめのクエリにおいて、 = を見ると、の次はです。
4 726 45 188 885 181 205 305 169 282 62 37 41
152 635 626 709 172 287 28 31
4 705114717 590136178 616807693 400822285 8708089 86329833 808186475 236869257 466568537 394895154 99700898 208593159
415141047 433903565 35546168 352395887 238027112 468849199 139333797 291512689