A12694. Tokitsukaze and Powers
编程题
普及/提高-
知识点
题目描述
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$ .
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$ .
输入格式
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.
It is guaranteed that $m$ is a positive integer power of a single prime number.
输出格式
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.
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.
输入输出样例
输入 #1
1 2 1
输出 #1
-1
输入 #2
3 5 1
输出 #2
2 4 3
输入 #3
2 5 4
输出 #3
2 3
输入 #4
4 9 8
输出 #4
2 4 7 5
说明/提示
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.
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.