NOI2012 随机数生成器
题目描述
栋栋最近迷上了随机算法，而随机数是生成随机算法的基础。栋栋准备使用线性同余法（Linear Congruential Method）来生成一个随机数列，这种方法需要设置四个非负整数参数 (m,a,c,X_0)，按照下面的公式生成出一系列随机数 ({X_n})：
其中(mod m) 表示前面的数除以 (m) 的余数。从这个式子可以看出，这个序列的下一个数总是由上一个数生成的。
栋栋知道这样产生的序列具有良好的随机性，不过心急的他仍然想尽快知道 (X_n) 是多少。由于栋栋需要的随机数是 (0,1,dots,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
说明/提示
计算得 (X_n=X_5=8)，故((X_n mod g) = (8 mod 3) = 2)。
对于 (100\%) 的数据，(n,m,a,c,X_0leq 10^{18})，(1leq gleq 10^8)，(n,mgeq 1)，(a,c,X_0geq 0)。
题意
给出了一个迷惑式子，让你算出来式子的第(n)项，然后(mod g)的结果
分析
看到这样一个个的递推式子，一个个用(for)循环来推肯定不行，所以很容易就会想到要用到矩阵快速幂来求。那么我们现在的主要任务就是构造矩阵来进行乘法运算。
首先看到题目中给出的式子：
取模运算可以暂且先不看，因为对结果没什么影响，在矩阵乘法的时候进行取模就行了。所以转化成如下式子：
那么我们就可以根据这个式子来构造矩阵。由矩阵的乘法运算为结果矩阵的(i)行(j)列为前边矩阵一个的第(i)行乘以另一个的第(j)列，所以我们可以得出如下的矩阵递推式子：
这里用(X_{n-1})这一列分别乘以右边矩阵的第一第二行，得到结果的矩阵，那么我们就可以根据这个递推式子来进行矩阵快速幂。
这里乘法的运算过程如下：
由此得到结果矩阵
这里的矩阵做乘法的时候需要用到龟速乘，不然会爆(long long)
代码
#include<bits/stdc++.h>
using namespace std;
#define int long long
struct Node{//矩阵结构体
int a[5][5];
};
int m,a,c,x0,g,n;
int ksj(int a,int b){//龟速乘
int ans = 0;
while(b){
if(b & 1)ans = (ans + a) % m;
a = (a + a) % m;
b >>= 1;
}
return ans;
}
Node Mul(Node a,Node b,int c){//矩阵乘法，记得取模
Node ans;
memset(ans.a,0,sizeof(ans.a));
for(int i=1;i<=2;++i){
for(int j=1;j<=2;++j){
for(int k=1;k<=2;++k){
ans.a[i][j] = (ans.a[i][j] + ksj(a.a[i][k],b.a[k][j])%c)%c;
}
}
}
return ans;
}
Node ans;
void qpow(Node &ans,Node b,int c){//矩阵快速幂
while(c){
if(c & 1)ans = Mul(b,ans,m);
b = Mul(b,b,m);
c >>= 1;
}
}
signed main(){
Node bas;
scanf("%lld%lld%lld%lld%lld%lld",&m,&a,&c,&x0,&n,&g);
ans.a[1][1] = x0;//初始化矩阵
ans.a[2][1] = c;
bas.a[1][1] = a;
bas.a[1][2] = 1;
bas.a[2][1] = 0;
bas.a[2][2] = 1;
qpow(ans,bas,n);
printf("%lld
",ans.a[1][1] % g);//得答案
}