打卡信奥刷题（2536）用C++实现信奥 P2044 [NOI2012] 随机数生成器

P2044 [NOI2012] 随机数生成器

题目描述

栋栋最近迷上了随机算法，而随机数是生成随机算法的基础。栋栋准备使用线性同余法（Linear Congruential Method）来生成一个随机数列，这种方法需要设置四个非负整数参数m , a , c , X 0 m,a,c,X_0m,a,c,X0​，按照下面的公式生成出一系列随机数{ X n } \{X_n\}{Xn​}：
X n + 1 = ( a X n + c ) m o d m X_{n+1}=(aX_n +c)\bmod mXn+1​=(aXn​+c)modm

其中m o d m \bmod mmodm表示前面的数除以m mm的余数。从这个式子可以看出，这个序列的下一个数总是由上一个数生成的。

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

栋栋知道这样产生的序列具有良好的随机性，不过心急的他仍然想尽快知道X n X_nXn​是多少。由于栋栋需要的随机数是0 , 1 , … , g − 1 0,1,\dots,g-10,1,…,g−1之间的，他需要将X n X_nXn​除以g gg取余得到他想要的数，即X n m o d g X_n \bmod gXn​modg，你只需要告诉栋栋他想要的数X n m o d g X_n \bmod gXn​modg是多少就可以了。

输入格式

一行6 66个用空格分割的整数m , a , c , X 0 , n m,a,c,X_0,nm,a,c,X0​,n和g gg，其中a , c , X 0 a,c,X_0a,c,X0​是非负整数，m , n , g m,n,gm,n,g是正整数。

输出格式

输出一个数，即X n m o d g X_n \bmod gXn​modg。

输入输出样例 #1

输入 #1

11 8 7 1 5 3

输出 #1

2

说明/提示

计算得X n = X 5 = 8 X_n=X_5=8Xn​=X5​=8，故( X n m o d g ) = ( 8 m o d 3 ) = 2 (X_n \bmod g) = (8 \bmod 3) = 2(Xn​modg)=(8mod3)=2。

对于100 % 100\%100%的数据，n , m , a , c , X 0 ≤ 1 0 18 n,m,a,c,X_0\leq 10^{18}n,m,a,c,X0​≤1018，1 ≤ g ≤ 1 0 8 1\leq g\leq 10^81≤g≤108，n , m ≥ 1 n,m\geq 1n,m≥1，a , c , X 0 ≥ 0 a,c,X_0\geq 0a,c,X0​≥0。

C++实现

#include<bits/stdc++.h>typedefunsignedlonglongull;usingnamespacestd;ull mod,a,c,x,n,g,mod1,m;ull ret,ans;inlineullmul(ull x,ull y){//龟速乘法for(ret=0;y;y>>=1){if(y&1)ret=(ret+x)%mod;x=(x+x)%mod;}returnret;}ullPow(ull a,ull k){//快速幂ull x=a;for(ans=1;k;k>>=1){if(k&1)ans=mul(ans,x);x=mul(x,x);}returnans;}ullSum(ull n,ull t){//n是长度 t是首项 m是公比if(n==1)returnt;ull ret=Sum(n/2,t);ret=(ret+mul(ret,Pow(m,n/2)))%mod;if(n&1)ret=(ret+mul(Pow(m,(n-1)),t))%mod;returnret;}intmain(){cin>>mod>>m>>c>>x>>n>>mod1;ull ans=Pow(m,n);ans=mul(ans,x);ans=(ans+Sum(n,c))%mod;cout<<ans%mod1;return0;}

后续

接下来我会不断用C++来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现，记录日常的编程生活、比赛心得，感兴趣的请关注，我后续将继续分享相关内容