Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
 User ID: Password:
Register
ACM ICPC 2018 World Finals
Language:
Random Gap
 Time Limit: 3000MS Memory Limit: 65536K Total Submissions: 5517 Accepted: 1483

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 = (aRn - 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 ≤ 107, 1 ≤ m ≤ 16000000, am + c < 232.

Output

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

Sample Input

```15 7 100 1
```

Sample Output

```25
```

Source

Northeastern Europe 2004, Far-Eastern Subregion

[Submit]   [Go Back]   [Status]   [Discuss]

All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator