P4296 [AHOI2007] Password Box

By chance, Little Keke obtained a password box said to contain an ancient treasure map. The box can be opened by cracking the password, and the ancient symbols engraved on the back of the box serve as hints. After painstaking deciphering, Little Keke discovered that these symbols describe a number and its relation to the password. Suppose this number is $n$, and the password is $x$. Then we have: the password $x$ is greater than or equal to $0$ and less than $n$, and the remainder of $x^2$ divided by $n$ is $1$. Little Keke knows there may be more than one $x$ that satisfies these conditions, so she must compute all such $x$; the correct password is among them. The computation is arduous—can you write a program to help?

One line containing an integer $n$ ($1 \leq n \leq 2 \times 10^9$).

Find all $x$ that satisfy the conditions described above. If no such $x$ exists, output a single line `None`. Otherwise, output these $x$ in increasing order, one per line.

Translated by ChatGPT 5