P - A^k=k
Editorial
/
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 800 点
問題文
T 個のケースについて、以下の問題を解いてください。
正整数 A,M が与えられます。 A^k \equiv k \pmod M を満たす非負整数 k\ (k < M \times \varphi (M)) の個数を求め(ans とします)、条件を満たす k を \min(ans,1000) 個構築してください。
ただし、 \varphi(M) はオイラーのファイ関数を表します。
制約
- 1 \le T \le 100
- 1 \leq A,M \leq 10^9
- 入力は全て整数
入力
入力は以下の形式で標準入力から与えられる。
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
1 2 4
出力例 1
1 4
2^4\equiv 4 \pmod 4 です。
原案: turtle0123__