A12050 | X-mouse in the Campus

The campus has $m$ rooms numbered from $0$ to $m - 1$ . Also the $x$ -mouse lives in the campus. The $x$ -mouse is not just a mouse: each second $x$ -mouse moves from room $i$ to the room $i \cdot x \mod{m}$ (in fact, it teleports from one room to another since it doesn't visit any intermediate room). Starting position of the $x$ -mouse is unknown.

You are responsible to catch the $x$ -mouse in the campus, so you are guessing about minimum possible number of traps (one trap in one room) you need to place. You are sure that if the $x$ -mouse enters a trapped room, it immediately gets caught.

And the only observation you made is $\text{GCD} (x, m) = 1$ .

The only line contains two integers $m$ and $x$ ( $2 \le m \le 10^{14}$ , $1 \le x < m$ , $\text{GCD} (x, m) = 1$ ) — the number of rooms and the parameter of $x$ -mouse.

Print the only integer — minimum number of traps you need to install to catch the $x$ -mouse.