Random Time Travel
Statement
Goal
A linear congruential generator (LCG) is a pseudorandom number generator algorithm defined by the recurrence relation:lcg(seed) = (a * seed + c) % m
LCGs are notably used by Java's Math.random(). It is sometimes useful to be able to check the value given by the random number generator a number of steps in the future or in the past, given the current internal seed of the LCG.
You are given the seed, the parameters a, c and m of an LCG and the number of steps.
If steps is positive you must return the result of the composition of the lcg function steps times.
lcg(lcg(...lcg(seed)))
If steps is negative you must return the result of the composition of the reverse of the lcg function.
lcg^-1(lcg^-1(...lcg^-1(seed)))
Hint: The reverse of an LCG is also an LCG. The composition of two LCGs is also an LCG.
Input
Line 1: Three space separated integers a, c and m for the LCG parameters.
Line 2: An integer seed
Line 3: An integer steps
Line 2: An integer seed
Line 3: An integer steps
Output
Line 1 : The output of the LCG, starting at seed and repeating steps times.
Constraints
0 ≤ a < 2^64
0 ≤ c < 2^64
1 ≤ m < 2^64, m is a power of 2
0 ≤ seed < 2^64
-2^63 <= steps < 2^63
0 ≤ c < 2^64
1 ≤ m < 2^64, m is a power of 2
0 ≤ seed < 2^64
-2^63 <= steps < 2^63
Example
Input
5 3 8 0 1
Output
3
Tags
Random, LCG, Seedfinding
Difficulty
Medium
Test cases
Simple forward Test
Input
5 3 8
0
1
Output
3
Validator 1 Validator
Input
5 3 8
3
1
Output
2
Simple backward Test
Input
5 3 8
3
-1
Output
0
Validator 2 Validator
Input
5 3 8
2
-1
Output
3
Java Random 10 steps Test
Input
25214903917 11 281474976710656
123456789
10
Output
265139739725951
NRC forward Validator
Input
1664525 1013904223 4294967296
56416741561
101456
Output
1133829513
Java Random -10 steps Test
Input
25214903917 11 281474976710656
123456789
-10
Output
41935260626811
NRC backward Validator
Input
1664525 1013904223 4294967296
95465457461
-4561
Output
3074731294
Back to the future Test
Input
25214903917 11 281474976710656
123456789
9007199254740990
Output
35623234005539
A long time ago Validator
Input
25214903917 11 281474976710656
123456789
-9007199254740991
Output
119305093197820
Solution language
Solution
Stub generator input