G - Simple Math Problem 2

2 secs 1024 MB
shobonvip's icon shobonvip

問題文

正整数 MM が与えられます。 0x<M0 \le x < M を満たす整数 xx であって、 x3x(modM)x^3 \equiv x \pmod M を満たすものをすべて求めてください。

制約

  • 1M10121 \le M \le 10^{12}
  • MM は整数

入力

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

MM

出力

条件を満たす xx がちょうど KK 個あるとし、それを A1,A2,,AKA_1, A_2, \cdots, A_Kiji \ne j なら AiAjA_i \ne A_j )とする。

11 行目には、 KK を出力せよ。

22 行目には、 A1,A2,,AKA_1, A_2, \dots, A_K を空白区切りで昇順に出力せよ。

注意

この問題の制約下で、出力すべき値の個数は 3×1053 \times 10^5 以下であることが証明される。

サンプル1

入力
5
出力
3
0 1 4

サンプル2

入力
1
出力
1
0

サンプル3

入力
20
出力
9
0 1 4 5 9 11 15 16 19

22 行目は昇順に出力する必要があることに注意してください。

Submit


Go (1.21)