POJ2381总结

Random Gap

题目来源

Description

The pseudo-random number genegators (or RNGs for short) are widely used in statistical calculations. One of the simplest and ubiquitious is the linear congruence RNG, that calculates the n-th random number Rn as Rn = (aR_{n – 1} + c) mod m, where a, c and m are constants. For example, the sequence for a = 15, c = 7, m = 100 and starting value R0 = 1 is 1, 22, 37, 62, 37, 62, …

Linear RNG is very fast, and can yield surprisinly good sequence of random numbers, given the right choice of constants. There are various measures of RNG quality, and your task is to calculate one of them, namely the longest gap between members of the sequence. More precisely, given the values of a, c, m, and R0, find such two elements Ri < Rj that:

1. there are no other Rk that Ri ≤ Rk ≤ Rj,
2. the difference Rj − Ri is maximal.

Input

Input contains integer numbers a c m R0.
0 ≤ a, c, R0 ≤ 10⁷, 1 ≤ m ≤ 16000000, am + c < 2³².

Output

Output should contain the single number — the maximal difference found.

Sample Input

15 7 100 1

Sample Output

25

我的代码

这个计算没有分支，一直算到出现了先前算过的为止。由于空间有限制，只够开一个数组，所以寻找最大值的时候要重新遍历所有的。

#include<stdio.h>
#include<string.h>

int a,c,m,r0,pre,now,max=0;
int flag[16000001];


int main()
{
	memset(flag,0,sizeof(flag));
	scanf("%d%d%d%d",&a,&c,&m,&r0);
	while (true){
		if (flag[r0]==0){
			flag[r0]=1;
			r0=(a*r0+c)%m;
		}else{
			break;
		}
	}
	for (int i=0;i<m;i++){
		if (flag[i]==1){
			pre=i;
			break;
		}
	}
	for (int i=pre+1;i<m;i++){
		if (flag[i]==1){
			max=max>i-pre?max:i-pre;
			pre=i;
		}
	}
	printf("%d\n",max);
	return 0;
}

反思

max需要赋初始值为0，因为有情况是算到最后只能得到一个值（a=1，c=0）。