X-mouse in the Campus
Contest: Educational Codeforces Round 49 (Rated for Div. 2)
Difficulty rating: 2600
Tags: bitmasks, math, number theory

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$$$.

Input format:
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.

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

Constraints:
Time limit: 1.5 s
Memory limit: 256.0 MB

Note:
In the first example you can, for example, put traps in rooms $$$0$$$, $$$2$$$, $$$3$$$. If the $$$x$$$-mouse starts in one of this rooms it will be caught immediately. If $$$x$$$-mouse starts in the $$$1$$$-st rooms then it will move to the room $$$3$$$, where it will be caught.

In the second example you can put one trap in room $$$0$$$ and one trap in any other room since $$$x$$$-mouse will visit all rooms $$$1..m-1$$$ if it will start in any of these rooms.

Example input:
4 3

Example output:
3

Example input:
5 2

Example output:
2

Editorial:
Some notes:
At first, there is $$$x^{-1} \mod{m}$$$ since $$$(x, m) = 1$$$ (lets define $$$\text{GCD}(a,b)$$$ as $$$(a, b)$$$). That means that for each $$$v = 0..m-1$$$ there is exactly one $$$u$$$ that $$$u \cdot x = v$$$. So if we look at this problem as the graph then it consists of cycles (consider loops as cycles of length one). So we need to know number of cycles in this graph.
At second, $$$(v, m) = (v \cdot x \mod{m}, m)$$$ since $$$(x, m) = 1$$$, $$$v \cdot x \mod{m} = v \cdot x - m \cdot k$$$ and $$$(v, m) \mid v$$$ and $$$(v, m) \mid m$$$. So all $$$v$$$ can be divided in groups by its $$$(v,m)$$$. And we can calculate number of cylces in each group independently.
Let fix some $$$\text{GCD}$$$ equal to $$$g$$$. All numbers $$$v$$$ such that $$$(v, m) = g$$$ can be represented as $$$v = g \cdot v'$$$ and $$$(v', m) = 1$$$. Number of such $$$v$$$ equals to $$$\varphi(\frac{m}{g})$$$. Moreover $$$gv' \cdot x \equiv gv' \cdot (x \mod{\frac{m}{g}}) \mod{m}$$$. Here we can shift from $$$v$$$, $$$x$$$ and $$$m$$$ to $$$v'$$$, $$$(x \mod{\frac{m}{g}})$$$ and $$$\frac{m}{g}$$$.
In result we need for each $$$d \mid m$$$ calculate number of cycles created by $$$x \mod{d}$$$ from numbers $$$v$$$, that $$$1 \le v < d$$$ and $$$(v, d) = 1$$$. Lets set $$$x = x \mod{d}$$$.
Next step is to find minimal $$$k > 0$$$ such that $$$x^k \equiv 1 \mod{d}$$$, let's name it order of $$$x$$$ or $$$\text{ord}(x)$$$. Then for each $$$0 \le i,j < k$$$ if $$$i \neq j$$$ then $$$x^i \not\equiv x^j$$$ and $$$v \cdot x^i \not\equiv v \cdot x^j$$$, so each cycle will have length equal to $$$\text{ord}(x)$$$ and number of cycles will be equal to $$$\frac{\varphi(d)}{\text{ord}(x \mod d)}$$$.
Last step is calculate $$$\text{ord}(x)$$$ for each $$$d \mid m$$$. There is a fact that $$$\text{ord}(x) \mid \varphi(d)$$$ so can try to iterate over all divisors $$$df$$$ of $$$\varphi(d)$$$ and check $$$x^{df} \equiv 1$$$ by binary exponentiation (It seems as $$$O(divs(m)^2 \log{m})$$$ but it's faster and author's version work around 2 seconds. It doesn't pass but somebody can write better). But we'll speed it up. Let $$$\varphi(d) = p_1^{a_1} p_2^{a_2} \dots p_k^{a_k}$$$. So we can independently for each $$$p_i$$$ find its minimal power $$$b_i \le a_i$$$ such that $$$x^{\varphi(d) \cdot p_i^{b_i - a_i}} \equiv 1$$$. We can just iterate over all $$$p_i$$$ and $$$a_i$$$ since $$$\sum{a_i} = O(\log{m})$$$.
Some words about finding $$$\varphi(d)$$$ — its factorization differs from factorization of $$$d$$$ just by lowering degrees of primes and adding factorizations of some $$$(p_i - 1)$$$. But we can manually find factorization of $$$(p_i - 1)$$$ with memorization (or even without it) since $$$\sum{\sqrt{p_i}} \le \prod{\sqrt{p_i}} = O(\sqrt{m})$$$.
So our steps are next: factorize $$$m$$$, recursively iterate over all divisors of $$$m$$$, find $$$\varphi(d)$$$ and $$$\text{ord}(x \mod d)$$$, and add to the answer $$$\frac{\varphi(d)}{\text{ord}(x \mod d)}$$$.
Result complexity is $$$O(\sqrt{m} + \text{divs}(m) \cdot \log^2{m})$$$.
And the last note is how to multiply $$$a, b < 10^{14}$$$ modulo $$$mod \le 10^{14}$$$. You can use binary multiplification which will give you extra $$$\log{m}$$$ what is not critically in this task (in C++, of course). Or you can use multiplification from hashes, which will work with 64 bit double, since it's only $$$10^{14}$$$.