31380번 - List of Powers 다국어

문제

Let $p$ be a prime number and $a$ an integer such that 0ドル < a < p$. Consider all integers from $l$ to $r$ inclusive which can be expressed as $a^{k} \bmod p$ for some non-negative integer $k$. Given that the number of such integers is at most 100ドル,ドル print these integers in ascending order.

입력

The only line contains four integers $p,ドル $a,ドル $l,ドル and $r$ separated by spaces (0ドル < a < p \le 10^{9},ドル $p$ is prime, 0ドル \le l \le r < p$).

출력

Print all integers from $l$ to $r$ inclusive which can be expressed as $a^{k} \bmod p$ for some non-negative integer $k$. The integers must be printed in ascending order. Separate consecutive integers by spaces. The input is guaranteed to be such that the correct answer contains at most 100ドル$ numbers.

제한

힌트

In the first example, we must find all integers from $l = 0$ up to $r = 3$ inclusive which can be expressed as 3ドル^{k} \bmod 5$ for some integer $k \ge 0$. These are numbers 3ドル^{0} \bmod 5 = 1,ドル 3ドル^{1} \bmod 5 = 3$ and 3ドル^{3} \bmod 5 = 27 \bmod 5 = 2$. The number 0ドル$ can not be expressed this way because 3ドル^{k}$ does not divide evenly by 5ドル$ for any integer $k \ge 0$. So, we must print the numbers 1ドル,ドル 2ドル,ドル and 3ドル$ in ascending order.

In the second example, we must find all integers from $l = 2$ up to $r = 3$ inclusive which can be expressed as 4ドル^{k} \bmod 5$ for some integer $k \ge 0$. Let us write down the first few such numbers: 4ドル^{0} \bmod 5 = 1,ドル 4ドル^{1} \bmod 5 = 4,ドル 4ドル^{2} \bmod 5 = 16 \bmod 5 = 1,ドル 4ドル^{3} \bmod 5 = 64 \bmod 5 = 4,ドル 4ドル^{4} \bmod 5 = 256 \bmod 5 = 1,ドル $\ldots$. It can be proved that this sequence contains only numbers 1ドル$ and 4ドル$. So, the result is an empty list.