题目链接

随机数生成器

题目描述

栋栋最近迷上了随机算法,而随机数生成是随机算法的基础。栋栋准备使用线性同余法(Linear Congruential Method)来生成一个随机数列,这种方法需要设置四个非负整数参数$m$,$a$,$c$,$X_0$,按照下面的公式生成出一系列随机数 $\{X_n\}$:
$X_{n+1}=$($aX_n+c$)$mod\ m$
其中$mod\ m$表示前面的数除以$m$的余数。从这个式子可以看出,这个序列的下一个数总是由上一个数生成的。

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

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

输入格式

一行$6$个用空格分割的整数$m$,$a$,$c$,$X_0$,$n$和$g$,其中$a$,$c$,$X_0$是非负整数,$m$,$n$,$g$ 是正整数。

输出格式

输出一个数,即$X_n\ mod\ g$。

样例输入

11 8 7 1 5 3

样例输出

2

数据范围

对于所有数据,$n \ge 1$,$m \ge 1$,$a \ge 0$,$c \ge 0$,$X_0 \ge 0$,$1 \ge g \ge 10^8$。

题解

题目很明显告诉你了$X_n$递推的性质,那么这道题很容易想到矩阵快速幂来加速。
矩阵的构造如下:

因为$X_n$的递推式里有一个常数$c$所以我们这里要加以个常数$1$来保证能传递。
上代码:

#include<bits/stdc++.h>
using namespace std;
long long m,a,c,x0,n,g;
struct aa{
    long long a[9][9];
};
long long kk(long long x,long long y){
    long long ans=0,u;
    int t=0;
    while(y){
        if(y&1) ans=(ans+x)%m;
        x<<=1;
        x%=m;
        y>>=1;
    }
    return ans;
}
aa cc(aa x,aa y){
    aa ans;
    for(int j=1;j<=2;j++)
        for(int i=1;i<=2;i++)
            ans.a[j][i]=(kk(x.a[j][1],y.a[1][i])+kk(x.a[j][2],y.a[2][i]))%m;
    return ans;
}
aa ksm(aa x,long long p){
    aa ans;
    for(int j=1;j<=2;j++)
        for(int i=1;i<=2;i++)
            ans.a[j][i]=(j==i);
    while(p){
        if(p&1) ans=cc(ans,x);
        x=cc(x,x);
        p>>=1;
    }
    return ans;
}
int main(){
    scanf("%lld%lld%lld%lld%lld%lld",&m,&a,&c,&x0,&n,&g);
    x0%=m;
    aa x;
    x.a[1][1]=a;
    x.a[1][2]=c;
    x.a[2][1]=0;
    x.a[2][2]=1;
    aa ans=ksm(x,n);
    printf("%lld\n",((kk(ans.a[1][1],x0)+ans.a[1][2])%m)%g);
    return 0;
}