Tokitsukaze and Powers
Contest: Codeforces Round 573 (Div. 1)
Difficulty rating: 3400
Tags: number theory, probabilities

Tokitsukaze is playing a room escape game designed by SkywalkerT. In this game, she needs to find out hidden clues in the room to reveal a way to escape.

After a while, she realizes that the only way to run away is to open the digital door lock since she accidentally went into a secret compartment and found some clues, which can be interpreted as:

- Only when you enter $$$n$$$ possible different passwords can you open the door;
- Passwords must be integers ranged from $$$0$$$ to $$$(m - 1)$$$;
- A password cannot be $$$x$$$ ($$$0 \leq x < m$$$) if $$$x$$$ and $$$m$$$ are not coprime (i.e. $$$x$$$ and $$$m$$$ have some common divisor greater than $$$1$$$);
- A password cannot be $$$x$$$ ($$$0 \leq x < m$$$) if there exist non-negative integers $$$e$$$ and $$$k$$$ such that $$$p^e = k m + x$$$, where $$$p$$$ is a secret integer;
- Any integer that doesn't break the above rules can be a password;
- Several integers are hidden in the room, but only one of them can be $$$p$$$.

Fortunately, she finds that $$$n$$$ and $$$m$$$ are recorded in the lock. However, what makes Tokitsukaze frustrated is that she doesn't do well in math. Now that she has found an integer that is suspected to be $$$p$$$, she wants you to help her find out $$$n$$$ possible passwords, or determine the integer cannot be $$$p$$$.

Input format:
The only line contains three integers $$$n$$$, $$$m$$$ and $$$p$$$ ($$$1 \leq n \leq 5 \times 10^5$$$, $$$1 \leq p < m \leq 10^{18}$$$).

It is guaranteed that $$$m$$$ is a positive integer power of a single prime number.

Output format:
If the number of possible different passwords is less than $$$n$$$, print a single integer $$$-1$$$.

Otherwise, print $$$n$$$ distinct integers ranged from $$$0$$$ to $$$(m - 1)$$$ as passwords. You can print these integers in any order. Besides, if there are multiple solutions, print any.

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

Note:
In the first example, there is no possible password.

In each of the last three examples, the given integer $$$n$$$ equals to the number of possible different passwords for the given integers $$$m$$$ and $$$p$$$, so if the order of numbers in the output is ignored, the solution is unique as shown above.

Example input:
1 2 1

Example output:
-1

Example input:
3 5 1

Example output:
2 4 3

Editorial:
Firstly, let me briefly review this problem for you. Given integers $$$n$$$, $$$m$$$ and $$$p$$$ ($$$n > 0$$$, $$$m > 1$$$, $$$p \neq 0$$$), we denote $$$S = \{x | x \in \mathbb{Z}, 0 \leq x < m, \gcd(m, x) = 1\}$$$ and $$$T = \{p^e \bmod m | e \in \mathbb{Z}, e \geq 0\}$$$, where $$$\gcd(m, x)$$$ means the greatest common divisor of $$$m$$$ and $$$x$$$, and you are asked to pick up $$$n$$$ distinct integers from $$$(S - T)$$$, the set of elements in $$$S$$$ but not in $$$T$$$, or report that it is unachievable. Besides, there is an additional restriction, $$$m = q^k$$$ for a prime number $$$q$$$ and a positive integer $$$k$$$.
It is not difficult to show $$$|S|$$$, the size of $$$S$$$, equals to $$$\varphi(m) = m (1 - \frac{1}{q})$$$. When $$$\gcd(m, p) > 1$$$, there is only one element $$$p^0 \bmod m = 1$$$ in $$$T$$$ which is coprime to $$$m$$$, so in that case, $$$|S - T| = \varphi(m) - 1$$$. To output a solution, you can just enumerate the smallest integers and skip the integer $$$1$$$ and any multiples of $$$q$$$. In this process, you won't need to enumerate more than $$$(2 n + 1)$$$ integers, because $$$\frac{n}{1 - \frac{1}{q}} + 1 \leq 2 n + 1$$$.
When $$$\gcd(m, p) = 1$$$, we can observe that $$$T \subseteq S$$$. Let $$$|T|$$$ be $$$\lambda$$$, and we may conclude from Euler's totient theorem that $$$\lambda \leq \varphi(m)$$$, and even $$$\lambda | \varphi(m)$$$. When $$$n > \varphi(m) - \lambda$$$, there is no solution, so we need to calculate $$$\lambda$$$ in order to determine the existence of solutions.
To calculate $$$\lambda$$$, you can just enumerate all the divisors of $$$\varphi(m)$$$ and check them using Fast Power Algorithm, because the number of divisors is not too large due to the restrictions. Alternatively, you can do it more advanced and check more efficiently like the following.
The above approach requires $$$\mathcal{O}(\log \varphi(m))$$$ calls of Fast Power Algorithm. It is used more regularly when searching a random primitive root in modulo some integer.
When implementing Fast Power Algorithm, you may notice an issue that the modular multiplication may not be easy to code, when the 128-bit integer operations are not directly provided on this platform. In a precise way, you can implement another like Fast Multiplying Algorithm, though it is a bit slow. But if you believe you are lucky enough and you prefer using C/C++, you can try the following code in a convenient way.
No matter what approach you used, the factorization of $$$(q - 1)$$$ is inevitable, so the problem requires you to factorize a relatively large number (less than $$$10^{18}$$$) a bit quickly. For example, you can use Pollard's Rho Algorithm with Miller-Rabin Primality Test. By Birthday Paradox, which is a heuristic claim, when $$$x$$$ is not a prime, Pollard's Rho Algorithm can split $$$x$$$ into $$$u \cdot v$$$ in $$$\mathcal{O}(\sqrt{\min\{u, v\}}) = \mathcal{O}(x^{1 / 4})$$$ iterations. By the way, you can obtain $$$q$$$ from $$$m$$$ by enumerating possible $$$k$$$ from large to small, instead of factorization.
Let's go back to the case that $$$\gcd(m, p) = 1$$$ and $$$n \leq \varphi(m) - \lambda$$$. When any solution exists, we can observe that $$$\varphi(m) - \lambda \geq \frac{\varphi(m)}{2}$$$, so there may exist some solutions based on random distribution. That is, if you are able to check whether an integer is in $$$T$$$ or not, you can roughly pick $$$2 n$$$ integers in $$$S$$$ and check them. One approach is like the mechanism built in the problem checker, but as space is limited, I would not expend it at here. One thing you should be aware of is that you can't pick them without checking, as the probability of failure may be so large, like $$$\frac{1}{2}$$$. Moreover, you can't use Baby-Step-Giant-Step Algorithm since its time complexity $$$\mathcal{O}(\sqrt{n m})$$$ is too slow.
If there exists at least one primitive root in modulo $$$m$$$, then we can construct the output integers. Since a primitive root $$$g$$$ can represent $$$S$$$ as $$$\{g^e \bmod m | e \in \mathbb{Z}, 0 \leq e < \varphi(m)\}$$$, we can reduce the problem into something about modular equation that only concerns the exponents. As the number of primitive root in modulo $$$m$$$ is $$$\varphi(\varphi(m))$$$, if the root exists, we can get a random primitive root easily. Now let's assume we find a primitive root $$$g$$$ and $$$p \equiv g^u \pmod{m}$$$. An integer $$$(g^v \bmod m)$$$ is in $$$T$$$ if and only if the equation $$$e u \equiv v \pmod{\varphi(m)}$$$ has a solution of $$$e$$$. It is easy to show, when $$$\gcd(\varphi(m), u) | v$$$, a solution of $$$e$$$ always exists. Furthermore, we can conclude $$$\lambda = \frac{\varphi(m)}{\gcd(\varphi(m), u)}$$$, so the construction is quite straightforward.
The only case we left is when no primitive root exists in modulo $$$m$$$, which occurs when $$$m = 2^k$$$, $$$k \geq 3$$$. In this case, we cannot represent all the elements in $$$S$$$ as non-negative integer powers of one specific number, but we can find a pseudo-primitive root $$$g'$$$ to use its powers to represent all the elements in the form of $$$(4 t + 1)$$$ in $$$S$$$ (as the group $$$(S, \times_m)$$$, as known as $$$(\mathbb{Z}/m\mathbb{Z})^{\times}$$$, is isomorphic to a direct product of cyclic groups, $$$\mathrm{C}_2 \times \mathrm{C}_{2^{k - 2}}$$$). Besides, $$$\{m - ({g'}^{e} \bmod m) | e \in \mathbb{Z}, 0 \leq e < 2^{k - 2}\}$$$ can represent the rest numbers (in the form of $$$(4 t + 3)$$$) in $$$S$$$. As the product of two integers in the form of $$$(4 t + 3)$$$ is in the form of $$$(4 t + 1)$$$, we can discuss the parity of $$$e$$$ in expression $$$(p^e \bmod m)$$$ and check if an integer is in $$$T$$$, so the construction could work after a little modification.
In summary, to solve this problem, we need to factorize $$$\varphi(m)$$$, calculate the order of $$$p$$$ in modulo $$$m$$$, find a primitive root $$$g$$$ (or a pseudo-primitive root $$$g'$$$) in modulo $$$m$$$ and enumerate some small integers (values or exponents) to construct a solution.
Time complexity: $$$\mathcal{O}((m^{1 / 4} + n) M(m))$$$, where $$$M(m)$$$ means the cost of one multiplication modulo $$$m$$$. Some slow solutions are accepted as well.