A5811. 「NOI2012」随机数生成器
编程题
普及+/提高
知识点
题目描述
栋栋最近迷上了随机算法，而随机数生成是随机算法的基础。栋栋准备使用线性同余法（Linear Congruential Method）来生成一个随机数列，这种方法需要设置四个非负整数参数 $m$，$a$，$c$，$X_0$，按照下面的公式生成出一系列随机数 $\lbrace X_n \rbrace$：
$$ X_{n+1} = (aX_n + c) \bmod m $$
其中$\bmod m$ 表示前面的数除以 $m$ 的余数。从这个式子可以看出，这个序列的下一个数总是由上一个数生成的。
用这种方法生成的序列具有随机序列的性质，因此这种方法被广泛地使用，包括常用的 C++和 Pascal 的产生随机数的库函数使用的也是这种方法。
栋栋知道这样产生的序列具有良好的随机性，不过心急的他仍然想尽快知道 $X_n$ 是多少。由于栋栋需要的随机数是 $0$，$1$，...，$g − 1$ 之间的，他需要将 $X_n$ 除以 $g$ 取余得到他想要的数，即 $X_n \bmod g$，你只需要告诉栋栋他想要的数 $X_n \bmod g$ 是
多少就可以了。
$$ X_{n+1} = (aX_n + c) \bmod m $$
其中$\bmod m$ 表示前面的数除以 $m$ 的余数。从这个式子可以看出，这个序列的下一个数总是由上一个数生成的。
用这种方法生成的序列具有随机序列的性质，因此这种方法被广泛地使用，包括常用的 C++和 Pascal 的产生随机数的库函数使用的也是这种方法。
栋栋知道这样产生的序列具有良好的随机性，不过心急的他仍然想尽快知道 $X_n$ 是多少。由于栋栋需要的随机数是 $0$，$1$，...，$g − 1$ 之间的，他需要将 $X_n$ 除以 $g$ 取余得到他想要的数，即 $X_n \bmod g$，你只需要告诉栋栋他想要的数 $X_n \bmod g$ 是
多少就可以了。
输入格式
一行 $6$ 个用空格分割的整数 $m$，$a$，$c$，$X_0$，$n$ 和 $g$，其中 $a$，$c$，$X_0$ 是非负整数，$m$，$n$，$g$ 是正整数。
输出格式
输出一个数，即 $X_n \bmod g$。
输入输出样例
输入 #1
11 8 7 1 5 3
输出 #1
2
说明/提示
| 测试点编号 | $n$ | $m,a,c,X_0$ | $m,a$ 性质 |
| :-: | :-: | :-: | :-: |
| 1 | $n \le 100$ | $m,a,c,X_0 \le 100$ | $m$ 为质数 |
| 2 | $n \le 1000$ | $m,a,c,X_0 \le 1000$ | $m$ 为质数 |
| 3 | $n \le 10^4$ | $m,a,c,X_0 \le 10^4$ | $m$ 为质数 |
| 4 | $n \le 10^4$ | $m,a,c,X_0 \le 10^4$ | $m$ 为质数 |
| 5 | $n \le 10^5$ | $m,a,c,X_0 \le 10^4$ | $m$ 与 $a-1$ 互质 |
| 6 | $n \le 10^5$ | $m,a,c,X_0 \le 10^4$ | $m$ 与 $a-1$ 互质 |
| 7 | $n \le 10^5$ | $m,a,c,X_0 \le 10^4$ | $m$ 与 $a-1$ 互质 |
| 8 | $n \le 10^6$ | $m,a,c,X_0 \le 10^4$ | - |
| 9 | $n \le 10^6$ | $m,a,c,X_0 \le 10^9$ | $m$ 为质数 |
| 10 | $n \le 10^6$ | $m,a,c,X_0 \le 10^9$ | - |
| 11 | $n \le 10^{12}$ | $m,a,c,X_0 \le 10^9$ | $m$ 为质数 |
| 12 | $n \le 10^{12}$ | $m,a,c,X_0 \le 10^9$ | $m$ 为质数 |
| 13 | $n \le 10^{16}$ | $m,a,c,X_0 \le 10^9$ | $m$ 与 $a-1$ 互质 |
| 14 | $n \le 10^{16}$ | $m,a,c,X_0 \le 10^9$ | $m$ 与 $a-1$ 互质 |
| 15 | $n \le 10^{16}$ | $m,a,c,X_0 \le 10^9$ | - |
| 16 | $n \le 10^{18}$ | $m,a,c,X_0 \le 10^9$ | - |
| 17 | $n \le 10^{18}$ | $m,a,c,X_0 \le 10^9$ | - |
| 18 | $n \le 10^{18}$ | $m,a,c,X_0 \le 10^{18}$ | $m$ 为质数 |
| 19 | $n \le 10^{18}$ | $m,a,c,X_0 \le 10^{18}$ | $m$ 与 $a-1$ 互质 |
| 20 | $n \le 10^{18}$ | $m,a,c,X_0 \le 10^{18}$ | - |
对于所有数据，$n \ge 1$，$m \ge 1$，$a \ge 0$，$c \ge 0$，$X_0 \ge 0$，$1\le g\le 10^8$。
| :-: | :-: | :-: | :-: |
| 1 | $n \le 100$ | $m,a,c,X_0 \le 100$ | $m$ 为质数 |
| 2 | $n \le 1000$ | $m,a,c,X_0 \le 1000$ | $m$ 为质数 |
| 3 | $n \le 10^4$ | $m,a,c,X_0 \le 10^4$ | $m$ 为质数 |
| 4 | $n \le 10^4$ | $m,a,c,X_0 \le 10^4$ | $m$ 为质数 |
| 5 | $n \le 10^5$ | $m,a,c,X_0 \le 10^4$ | $m$ 与 $a-1$ 互质 |
| 6 | $n \le 10^5$ | $m,a,c,X_0 \le 10^4$ | $m$ 与 $a-1$ 互质 |
| 7 | $n \le 10^5$ | $m,a,c,X_0 \le 10^4$ | $m$ 与 $a-1$ 互质 |
| 8 | $n \le 10^6$ | $m,a,c,X_0 \le 10^4$ | - |
| 9 | $n \le 10^6$ | $m,a,c,X_0 \le 10^9$ | $m$ 为质数 |
| 10 | $n \le 10^6$ | $m,a,c,X_0 \le 10^9$ | - |
| 11 | $n \le 10^{12}$ | $m,a,c,X_0 \le 10^9$ | $m$ 为质数 |
| 12 | $n \le 10^{12}$ | $m,a,c,X_0 \le 10^9$ | $m$ 为质数 |
| 13 | $n \le 10^{16}$ | $m,a,c,X_0 \le 10^9$ | $m$ 与 $a-1$ 互质 |
| 14 | $n \le 10^{16}$ | $m,a,c,X_0 \le 10^9$ | $m$ 与 $a-1$ 互质 |
| 15 | $n \le 10^{16}$ | $m,a,c,X_0 \le 10^9$ | - |
| 16 | $n \le 10^{18}$ | $m,a,c,X_0 \le 10^9$ | - |
| 17 | $n \le 10^{18}$ | $m,a,c,X_0 \le 10^9$ | - |
| 18 | $n \le 10^{18}$ | $m,a,c,X_0 \le 10^{18}$ | $m$ 为质数 |
| 19 | $n \le 10^{18}$ | $m,a,c,X_0 \le 10^{18}$ | $m$ 与 $a-1$ 互质 |
| 20 | $n \le 10^{18}$ | $m,a,c,X_0 \le 10^{18}$ | - |
对于所有数据，$n \ge 1$，$m \ge 1$，$a \ge 0$，$c \ge 0$，$X_0 \ge 0$，$1\le g\le 10^8$。