2022浙江工业大学程序设计迎新赛——决赛J题题解-创新互联

Pseudorandom Number Generator

Description

伪随机数生成器 (Pseudorandom Number Generator, PRNG) 是用于生成接近于绝对随机数序列的数字序列的算法。一般来说，伪随机数生成器依赖于一个初始值，也称为种子，来生成对应的伪随机数序列。只要种子确定，使用伪随机数生成器生成的随机数就是完全确定的，因此其生成的随机数序列并不是真正随机的。

生成伪随机数的方法非常多，例如，我们可以通过以下方法得到 [0, p - 1] 范围内伪随机整数。

int seed = 初始种子, a = 初始参数, p = 初始参数;
int generate() {
    seed = (seed * seed + a) % p;
    return seed;
}

换句话说，假设初始参数 seed, a, p 给定，我们生成的随机数序列实际上是

f(seed),f(f(seed)),f(f(f(seed))),⋯

不过，可以注意到，每次生成的随机数由上一个随机数唯一确定，经过一定次数的迭代后，必然会陷入一个循环，我们称这个循环的循环节为这个随机数序列的周期。

现在，给定 seed, a 和 p，你需要计算使用该方法生成的随机数序列的周期。

Input

输入共一行，包含三个整数 seed, a, p(0≤seed,a

Output

输出共一行，包含一个整数，表示生成的随机数序列的周期。

Sample Input 1 

1 14 514

Sample Output 1

18

Hint

生成的序列的前 30 项为 15, 239, 81, 407, 155, 395, 297, 329, 315, 37, 355, 109, 73, 203, 103, 343, 471, 321, 255, 275, 81, 407, 155, 395, 297,329, 315, 37, 355, 109。

可以看到，从第三个随机数 8181 开始，之后的序列周期性出现，周期为 1818。

先打出来检索的代码，再来插旗子判断即可：

#includeusing namespace std;
const int N=10000010;
int aa[N],b[N]={},c[N];
int main()
{
	long long seed,a,p;
	cin >>seed >>a >>p;
	aa[1]=seed;
	int cnt=0;
	for(int i=1;;i++)
	{
		seed=(seed*seed+a)%p;
		aa[i]=seed;
		// aa[i+1]=(aa[i]*aa[i]+a)%p;
		b[seed]++;
		
		if(b[seed]==2)
		{
			cnt=i;
			break;
		}
		// cout<

数组要开到范围外，我因为数组不对wa了12发，一直run time error，麻了，悲

你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧