题目描述
栋栋最近迷上了随机算法，而随机数是生成随机算法的基础。栋栋准备使用线性同余法（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 2 |
11 8 7 1 5 3 |
输出样例
|
1 2 |
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
题解
其实挺简单的……B君讲的时候居然没听懂
在草稿纸上写一写
x[1]=(ax[0]+c)(mod\ m)
x[2]=a((ax[0]+c)+c)=a^2x[0]+ac+c(mod\ m)
x[3]=a(a^2x[0]+ac+c)+c=a^3x[0]+a^2c+ac+c(mod\ m)
蛮好，这样就可以推出：
x[n]=a^nx[0]+a^{n-1}c+\cdots+ac+c
第一项快速幂算出即可，后面n项为等比数列，递归求出即可，由于会爆long long，乘法用龟速乘代替即可
代码
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 |
#include<bits/stdc++.h> using namespace std; typedef unsigned long long ull; ull mod,a,c,x,n,g,mod1,m; ull mul(ull a,ull b){ ull ans=0; while(b){ if(b&1)ans=(ans+a)%mod; a=(a+a)%mod; b>>=1; } return ans; } ull qpow(ull a,ull b){ ull ans=1; while(b){ if(b&1)ans=mul(ans,a)%mod; a=mul(a,a)%mod; b>>=1; } return ans; } ull sum(ull n,ull t){ if(n==1)return t; ull res=sum(n/2,t); res=(res+mul(res,qpow(m,n/2)))%mod; if(n&1)res=(res+mul(qpow(m,(n-1)),t))%mod; return res; } int main(){ cin>>mod>>m>>c>>x>>n>>mod1; ull ans=qpow(m,n); ans=mul(ans,x); ans=(ans+sum(n,c))%mod; cout<<ans%mod1; return 0; } |