[NOI2012]随机数生成器

NC17649. [NOI2012]随机数生成器

描述

栋栋最近迷上了随机算法，而随机数生成是随机算法的基础。栋栋准备使用线性同余法（Linear Congruential Method）来生成一个随机数列，这种方法需要
设置四个非负整数参数 𝑚, 𝑎, 𝑐, 𝑋0，按照下面的公式生成出一系列随机数<𝑋𝑛>：
𝑋𝑛+1 = (𝑎𝑋𝑛 + 𝑐) 𝒎𝒐𝒅 𝑚
其中 𝒎𝒐𝒅 𝑚 表示前面的数除以 𝑚 的余数。从这个式子可以看出，这个序列的下一个数总是由上一个数生成的。
用这种方法生成的序列具有随机序列的性质，因此这种方法被广泛地使用，包括常用的C++和Pascal 的产生随机数的库函数使用的也是这种方法。
栋栋知道这样产生的序列具有良好的随机性，不过心急的他仍然想尽快知道𝑋𝑛 是多少。由于栋栋需要的随机数是0, 1, … , 𝑔 − 1 之间的，他需要将 𝑋𝑛 除以 𝑔取余得到他想要的数，即 𝑋𝑛 𝒎𝒐𝒅 𝑔，你只需要告诉栋栋他想要的数𝑋𝑛 𝒎𝒐𝒅 𝑔 是多少就可以了。

输入描述

包含6 个用空格分割的整数 𝑚, 𝑎, 𝑐, 𝑋₀, 𝑛 和 𝑔 ，其中𝑎, 𝑐, 𝑋₀ 是非负整数，𝑚, 𝑛, 𝑔 是正整数。

输出描述

输出一个数，即 𝑋𝑛 𝒎𝒐𝒅 𝑔。

示例1

输入:

11 8 7 1 5 3

输出:

说明:

上次编辑到这里，代码来自缓存点击恢复默认模板

Python3 解法, 执行用时: 55ms, 内存消耗: 6800K, 提交时间: 2021-06-03 17:08:04

o,a,c,x0,n,g=map(int,input().split())
b = []
while True:
    s = n // 2
    b.append(n % 2)
    if s == 0:
        break
    n = s
oo = [a, 0, c, 1]
a = [x0, 1]


def x(a, b):
    m = a[0];n = a[1]
    a[0] = (m * b[0] + n * b[2])%o
    a[1] = m * b[1] + n * b[3]


def y(a):
    m = a[0];n = a[1];p = a[2];q = a[3]
    a[0] = (m * m + n * p)%o
    a[1] = (m * n + n * q)%o
    a[2] = (p * m + q * p)%o
    a[3] = (p * n + q * q)%o


if b[0] == 1:
    x(a, oo)
for i in range(len(b) - 1):
    y(oo)
    if b[i + 1] == 1:
        x(a, oo)
print(a[0] % g)

C++(clang++ 11.0.1) 解法, 执行用时: 3ms, 内存消耗: 476K, 提交时间: 2022-10-23 14:45:57

#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll f(ll x,ll y,ll m){
	ll ans=0;
	while(y){
		if(y&1)ans=(ans+x)%m;
		x=(x<<1)%m,y>>=1;
	}
	return ans;
}
ll A,C,m,a,c,x,n,g;
int main(){
	cin>>m>>a>>c>>x>>n>>g;
	A=1,C=0;
	while(n){
		if(n&1)C=(C+f(A,c,m))%m,A=f(A,a,m)%m;
		c=(c+f(a,c,m))%m,a=f(a,a,m)%m,n>>=1;
	}
	cout<<(f(A,x,m)+C)%m%g;
}