НачалоПодразделы
| 996. Топики |
| 997. День бульдозериста |
| 998. Дружба и кефир |
| 999. Ближайшая стенка |
| 1000. Салют |
| 1001. rrrrr... |
| 1002. Отпуск программиста |
| 1003. Random Gap |
| 1004. Radio Coverage |
Дата и время
22/12/2024 16:01:44
Лето 8
A. Топики B. День бульдозериста C. Дружба и кефир D. Ближайшая стенка E. Салют F. rrrrr... G. Отпуск программиста H. Random Gap I. Radio Coverage
H. Random Gap
Техника программирования, моделированиеСтруктуры данных
Олимпиадные задачи на английском языке
| 03/07/2008 | Лето 2008 дорешивание ( 8H) |
| 18/07/2008 | Лето 2008 - 8 (H) |
Ограничения: время – 5s/10s, память – 8MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод 
Послать решение Blockly Посылки Темы Где Обсудить (0)
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\ =\ (a*R_{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_0\ =\ 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_0`,
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
Input file contains integer numbers `a` `c` `m` `R_0`.
Output
Output file should contain the single number – the maximal difference found.
Constraints
`0\ ≤\ a,\ c,\ R_0\ ≤\ 10^7`,
`1\ ≤\ m\ ≤\ 16\ 000\ 000`,
`a*m\ +\ c\ <\ 2^32`.
Sample Input 1
15 7 100 1
Sample Output 1
25
Sample Input 2
2 0 127 5
Sample Output 2
26
