#P2670. 「NOI2012」随机数生成器

「NOI2012」随机数生成器

题目描述

栋栋最近迷上了随机算法，而随机数生成是随机算法的基础。栋栋准备使用线性同余法（Linear Congruential Method）来生成一个随机数列，这种方法需要设置四个非负整数参数 mm，aa，cc，X0X_0，按照下面的公式生成出一系列随机数 {Xn}\lbrace X_n \rbrace：

Xn+1=(aXn+c) mod mX_{n+1} = (aX_n + c) \bmod m

其中 mod m\bmod m 表示前面的数除以 mm 的余数。从这个式子可以看出，这个序列的下一个数总是由上一个数生成的。

用这种方法生成的序列具有随机序列的性质，因此这种方法被广泛地使用，包括常用的 C++和 Pascal 的产生随机数的库函数使用的也是这种方法。

栋栋知道这样产生的序列具有良好的随机性，不过心急的他仍然想尽快知道 XnX_n 是多少。由于栋栋需要的随机数是 00，11，...，g−1g − 1 之间的，他需要将 XnX_n 除以 gg 取余得到他想要的数，即 Xn mod gX_n \bmod g，你只需要告诉栋栋他想要的数 Xn mod gX_n \bmod g 是 多少就可以了。

输入格式

一行 66 个用空格分割的整数 mm，aa，cc，X0X_0，nn 和 gg，其中 aa，cc，X0X_0 是非负整数，mm，nn，gg 是正整数。

输出格式

输出一个数，即 Xn mod gX_n \bmod g。

11 8 7 1 5 3

2

数据范围与提示

测试点编号 nn m,a,c,X0m,a,c,X_0 m,am,a 性质
1 n≤100n \le 100 m,a,c,X0≤100m,a,c,X_0 \le 100 mm 为质数
2 n≤1000n \le 1000 m,a,c,X0≤1000m,a,c,X_0 \le 1000
3 n≤104n \le 10^4 m,a,c,X0≤104m,a,c,X_0 \le 10^4
4
5 n≤105n \le 10^5 mm 与 a−1a-1 互质
6
7
8 n≤106n \le 10^6 -
9 m,a,c,X0≤109m,a,c,X_0 \le 10^9 mm 为质数
10 -
11 n≤1012n \le 10^{12} mm 为质数
12
13 n≤1016n \le 10^{16} mm 与 a−1a-1 互质
14
15 -
16 n≤1018n \le 10^{18}
17
18 m,a,c,X0≤1018m,a,c,X_0 \le 10^{18} mm 为质数
19 mm 与 a−1a-1 互质
20 -
对于所有数据，n≥1n \ge 1，m≥1m \ge 1，a≥0a \ge 0，c≥0c \ge 0，X0≥0X_0 \ge 0，1≤g≤1081\le g\le 10^8。
  1. 关于
  2. 联系我们
  3. 隐私
  4. 服务条款
  5. 版权申诉
  6. Language
  7. 兼容模式
  8. 主题
  2. © 2021-2024 Hydro.ac
  4. Worker 2 in 53ms
  5. Hydro v4.15.0 Professional