P - A^k=k

Contest Duration: 2022-03-28 09:00:00+0900 - 2022-03-28 11:30:00+0900 (local time) (150 minutes)

P - A^k=k Editorial

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 800 点

T 個のケースについて、以下の問題を解いてください。

正整数 A,M が与えられます。 A^k \equiv k \pmod M を満たす非負整数 k\ (k < M \times \varphi (M)) の個数を求め(ans とします)、条件を満たす k を \min(ans,1000) 個構築してください。

ただし、 \varphi(M) はオイラーのファイ関数を表します。

入力は以下の形式で標準入力から与えられる。

T
\mathrm{case}_1
\mathrm{case}_2
\vdots
\mathrm{case}_T

各ケースは以下の形式で与えられる。

A M

2T 行出力せよ。 2i-1 から 2i 行目には、 \mathrm{case}_i に対する答えを出力せよ。

各ケースについては、初めの行に問題文中で定義される ans を、次の行に空白区切りで条件を満たす k を \min(ans,1000) 個出力せよ。

ただし、出力する k はすべて相異なる必要がある。

1
2 4

1
4

2^4\equiv 4 \pmod 4 です。