DoubleRandom | Topcoder Archive

Problem Statement

One particular type of random number generator is called a lagged Fibonacci generator. The nth random number generated is denoted F(n). Similar to the Fibonacci sequence, F is defined recursively as:

     F( n ) = ( F( n-24 ) + F( n-55 ) ) mod m     for n >= 55 .

m must be defined before hand. A problem with such a generator is that you need 55 "setup values" to get the generator started. These 55 integers will be the values for F(0), F(1), ..., F(54). To obtain these setup values we will use a different kind of random number generator called a linear congruential generator. The kth random number generated by such a generator is denoted X(k). X is defined recursively as:

     X( k ) = ( a*X( k-1 ) + c ) mod m     for k >= 1 .

m, a, c, and X(0) must be defined before hand.

In this problem you will be given m, a, and c as well as x0 which is X(0). You will use the linear congruential generator to produce 55 values for the lagged fibonacci generator. In other words F(0) = X(0), F(1) = X(1), ..., F(54) = X(54). You will then, using the same m value as in the linear congruential generator, compute and return F(n) for the given n.

Definition

Class:: DoubleRandom
Method:: getRandom
Parameters:: int, int, int, int, int
Returns:: int
Method signature:: int getRandom(int n, int x0, int a, int c, int m)
(be sure your method is public)

Notes

In both formulas above, mod denotes the modulus operation written as % in many programming languages.

Constraints

a and c will be between 0 and 1000 inclusive.
m will be between 2 and 1000000 inclusive.
n will be between 0 and 1000000 inclusive.
x0 will be between 0 and m-1 inclusive.

Examples

```
0
```
```
0
```
```
3
```
```
2
```
```
10
```
```
Returns: 0
```
Here we are asking for F(0) = X(0) = x0. Thus we return 0.
```
3
```
```
0
```
```
3
```
```
2
```
```
10
```
```
Returns: 6
```
Here we need to compute F(3) = X(3). We know that X(0) = x0 = 0 X(1) = (3*X(0) + 2) % 10 = 2 % 10 = 2 X(2) = (3*X(1) + 2) % 10 = 8 % 10 = 8 X(3) = (3*X(2) + 2) % 10 = 26 % 10 = 6
```
31
```
```
0
```
```
3
```
```
2
```
```
10
```
```
Returns: 6
```
```
55
```
```
0
```
```
3
```
```
2
```
```
10
```
```
Returns: 6
```
Here we want F(55) = ( F(31) + F(0) ) % 10 = (6 + 0) % 10 = 6
```
1000000
```
```
0
```
```
3
```
```
2
```
```
10
```
```
Returns: 2
```
1000000 is big.
```
1000000
```
```
234234
```
```
17
```
```
943
```
```
999997
```
```
Returns: 928311
```

This problem statement is the exclusive and proprietary property of Topcoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of Topcoder, Inc. is strictly prohibited. (c)2024, Topcoder, Inc. All rights reserved.