← 返回题目列表

AtCoder · highrate2025_b

B. 三次根

中文机器翻译题面 查看原题

問題文

正整数 M 。 请解决以下有关x = 0, 1, \dots, M - 1 的问题。 满足

  • y ^ 3 \equiv x \pmod{M} 小于 M 的非负整数 请输出 y 从 1 件。然而,这样的 如果 y 不存在,则 输出 -1 。 由于它不满足

制約

  • M 是 1 以上 10^6 的整数

入力

输入将以以下形式通过标准输入给出。

M

出力

M 行。 当i 在线 x = i - 1 时打印答案。
如果有多个答案,则可以输出任意一个。


入力例 1

4

出力例 1

2
1
-1
3

各 x 的答案是: 当

  • x = 0 时,y = 2 然后 2^3 = 8 \equiv 0 \pmod{4} 成立。因此 y = 2 。
  • x = 1 时,y = 1 然后 1^3 = 1 \equiv 1 \pmod{4} 成立。因此 y = 1 。
  • x = 2 满足条件 y 不存在。因此 -1 。
  • x = 3 时,y = 3 然后 3^3 = 27 \equiv 3 \pmod{4} 成立。因此 y = 3 。

入力例 2

7

出力例 2

0
4
-1
-1
-1
-1
6

入力例 3

10

出力例 3

0
1
8
7
4
5
6
3
2
9