这又是一道国赛水题

题目描述

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

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

 

输入输出样例

输入样例#1： 

11 8 7 1 5 3

输出样例#1： 

2

说明

计算得X[n]=X[5]=8,故(X[n] mod g) = (8 mod 3) = 2

100%的数据中n,m,a,c,X[0]<=10^18,g<=10^8

这道题真的是很水很水很水的，思路非常的好像，就是这样的一个矩阵

 

\[\left( {\begin{array}{*{20}{c}}

{

{X_n}}&1\\

{}&{}

\end{array}} \right) = \left( {\begin{array}{*{20}{c}}

{

{X_{n - 1}}}&1\\

{}&{}

\end{array}} \right)*\left( {\begin{array}{*{20}{c}}

{

{a_{}}}&0\\

c&1

\end{array}} \right)\]

还有一点要注意，就是要用龟速乘！！

看题发现数据范围很大的一定要用快速乘避免溢出！！！！！！

上代码

1 #include
     
       2 #include
      
        3 #include
       
         4 using namespace std; 5 typedef long long lt; 6 lt m,a,c,X[0],n,g; 7 lt ksc(lt a,lt b,lt mod) 8 { 9     lt fina=0,kk=1;10     if(b<0)b=-b,kk=-kk;11     if(a<0)a=-a,kk=-kk;12     while(b)13     {14         if(b%2)fina=(fina+a)%mod;15         b>>=1,a=(a+a)%mod;16     }17     return fina%mod;18 }19 struct matrix20 {21     lt a[2][2];22     friend matrix operator*(matrix a,matrix b)23     {24         matrix ans;memset(ans.a,0,sizeof(ans.a));25         for(int i=0;i<2;i++)26             for(int j=0;j<2;j++)27                 for(int k=0;k<2;k++)28                     ans.a[i][j]=(ans.a[i][j]+ksc(a.a[i][k],b.a[k][j],m))%m;29         return ans;30     }31     friend matrix operator^(matrix a,lt k)32     {33         matrix ans;memset(ans.a,0,sizeof(ans.a));34         ans.a[0][0]=ans.a[1][1]=1;35         while(k)36         {37             if(k%2)ans=ans*a;38             k>>=1,a=a*a;39         }40         return ans;41     }42 }key,im;43 int main()44 {45     //freopen("testdata.in","r",stdin);46     scanf("%lld%lld%lld%lld%lld%lld",&m,&a,&c,&X[0],&n,&g);    47     key.a[0][0]=a,key.a[1][0]=c,key.a[0][1]=0,key.a[1][1]=1;48     key=key^n;49     im.a[0][0]=X[0],im.a[0][1]=1;50     im=im*key;51     printf("%lld",im.a[0][0]%m%g);52 }