#P3068. [NOI2012] 随机数生成器

    ID: 1210 传统题 1000ms 256MiB 尝试: 0 已通过: 0 难度: (无) 上传者: 标签>贪心数论质数筛法数学2012矩阵运算NOI素数判断矩阵乘法

[NOI2012] 随机数生成器

题目描述

栋栋最近迷上了随机算法,而随机数是生成随机算法的基础。栋栋准备使用线性同余法(Linear Congruential Method)来生成一个随机数列,这种方法需要设置四个非负整数参数 m,a,c,X0m,a,c,X_0,按照下面的公式生成出一系列随机数 {Xn}\{X_n\}

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

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

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

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

输入格式

一行 66 个用空格分割的整数 m,a,c,X0,nm,a,c,X_0,ngg,其中 a,c,X0a,c,X_0 是非负整数,m,n,gm,n,g 是正整数。

输出格式

输出一个数,即 XnmodgX_n \bmod g

11 8 7 1 5 3
2

提示

计算得 Xn=X5=8X_n=X_5=8,故(Xnmodg)=(8mod3)=2(X_n \bmod g) = (8 \bmod 3) = 2

对于 100%100\% 的数据,n,m,a,c,X01018n,m,a,c,X_0\leq 10^{18}1g1081\leq g\leq 10^8n,m1n,m\geq 1a,c,X00a,c,X_0\geq 0