题目描述
栋栋最近迷上了随机算法，而随机数生成是随机算法的基础。栋栋准备使用线性同余法（Linear Congruential Method）来生成一个随机数列，这种方法需要设置四个非负整数参数 m，a，c，X0，按照下面的公式生成出一系列随机数 {Xn}：Xn+1=(aXn+c)modm
其中modm 表示前面的数除以 m 的余数。从这个式子可以看出，这个序列的下一个数总是由上一个数生成的。
用这种方法生成的序列具有随机序列的性质，因此这种方法被广泛地使用，包括常用的 C++和 Pascal 的产生随机数的库函数使用的也是这种方法。
栋栋知道这样产生的序列具有良好的随机性，不过心急的他仍然想尽快知道 Xn 是多少。由于栋栋需要的随机数是 0，1，...，g−1 之间的，他需要将 Xn 除以 g 取余得到他想要的数，即 Xnmodg，你只需要告诉栋栋他想要的数 Xnmodg 是 多少就可以了。
输入格式
一行 6 个用空格分割的整数 m,a,c,X0,n 和 g，其中 a,c,X0 是非负整数，m,n,g 是正整数。
输出格式
输出一个数，即 Xnmodg。
#include<bits/stdc++.h>
#define mul(x,y) Wuguidechengfa(x,y)
using namespace std;
typedef long long ll;
const int N=40;
inline ll read()
{
char c;ll res=0;
for(;!isdigit(c);c=getchar());
for(;isdigit(c);c=getchar())res=(res<<3)+(res<<1)+(c^48);
return res;
}
ll mod,a,c,x0,n,g;
ll Wuguidechengfa(ll x,ll y)
{
ll ans=0;
while(y)
{
if(y&1) (ans+=x)%=mod;
(x+=x)%=mod;
y>>=1;
}
return ans;
}
struct Mat
{
ll a[N][N];
int n,m;
Mat(){n=m=0;memset(a,0,sizeof a);}
Mat(int k){n=m=k;memset(a,0,sizeof a);for(int i=1;i<=k;i++)a[i][i]=1;}
Mat(int x,int y){n=x,m=y;memset(a,0,sizeof a);}
Mat operator *(Mat b)
{
Mat c(n,b.m);
for(int i=1;i<=c.n;i++)
{
for(int j=1;j<=c.m;j++)
{
for(int k=1;k<=m;k++)
{
c.a[i][j]=(c.a[i][j]+mul(a[i][k],b.a[k][j]))%mod;
}
}
}
return c;
}
Mat operator *=(Mat b)
{
return *this=*this*b;
}
Mat operator ^(ll k)
{
Mat ans(n),t=*this;
while(k)
{
if(k&1) ans*=t;
t*=t;
k>>=1;
}
return ans;
}
Mat operator ^=(ll k)
{
return *this=*this^k;
}
};
int main()
{
mod=read();a=read();c=read();x0=read();n=read();g=read();
if(!n)return printf("%d\n",x0)&0;
Mat res(4,4);
res.a[1][1]=a,res.a[1][2]=1,res.a[2][2]=1;
Mat p(2,1);
p.a[1][1]=x0,p.a[2][1]=c;
res^=n;
res*=p;
printf("%lld\n",res.a[1][1]%g);
return 0;
}