【wiki1281】Xn数列

2014年3月3日1,5180

题目描述 Description

给你6个数,m, a, c, x0, n, g

Xn+1 = ( aXn + c ) mod m,求Xn

m, a, c, x0, n, g<=10^18

输入描述 Input Description

一行六个数 m, a, c, x0, n, g

输出描述 Output Description

输出一个数 Xn mod g

样例输入 Sample Input

11 8 7 1 5 3

样例输出 Sample Output

2

数据范围及提示 Data Size & Hint

int64按位相乘可以不要用高精度。

题解

由题目中 Xn+1 = (a * Xn + c) % m 可得以下矩阵:
┏ a, 0 ┓
[Xn, c] * ┃        ┃ = [Xn+1, c]
┗ 1, 1 ┛

 

于是做矩阵快速幂即可。

 

注意到m, a, c, x0, n, g <= 1018,其中a,c,X0 是非负整数,m,n,g 是正整数,所以我们对于取模运算进行一个修改,将乘法修改为倍增乘法(类似于快速幂):

long long Multiply (long long x, long long y)
{
long long ans = 0;
while(y)
{
if(y & 1) ans = (ans + x) % m;
x = (x << 1) % m;
y >>= 1;
}
return ans;
}