\(d[i]\) を「\(j^3 \equiv i \bmod M\) を満たす \(j\) の値一つ、ただし存在しなければ \(-1\)」と定義します。

各 \(d\) の値は以下のようにして求めることができます：

• \(d[0]=d[1]=\ldots=d[M-1]=-1\) とする。
• \(j=0,1,\ldots,M-1\) の順に \(d[j^3\bmod M] \leftarrow j\) とする。

以上を適切に実装することでこの問題に正答することができます。計算量は \(O(M)\) です。

実装例(Python3)

m = int(input())
d = [-1] * m
for j in range(m):
  d[j*j*j%m] = j
for i in d:
  print(i)