Имя: Пароль: Зарегистрироваться Восстановить пароль
10/12/2023 01:55:38

# Рабочее место участника

## Задачи

1003. Random Gap

Ограничения: время – 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

Source: A. Klenin, ICPC NEERC Far-Eastern subregional, 2004