ACM 2004 - Random Gap

Problem C. Random Gap ≡

problems
visible spaces
basic formulae
wide text
editor

Author:	A. Klenin	Time limit:	8 sec
Input file:	input.txt	Memory limit:	2 Mb
Output file:	output.txt

Statement

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 R_n as R_n = (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 R₀ = 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 R₀, find such two elements R_i < R_j that:

there are no other R_k R_i ≤ R_k ≤ R_j,
the difference R_j − R_i is maximal.

Input file format

Input file contains integer numbers a c m R₀.

Output file format

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

Constraints

0 ≤ a, c, R₀ ≤ 10⁷, 1 ≤ m ≤ 16000000, am + c < 2³².

Sample tests

No.	Input file (`input.txt`)	Output file (`output.txt`)
1	`15 7 100 1`	`25`
2	`2 0 127 5`	`26`