National Olympiad in Informatics, China, 2012
Day 1, Problem 1 - Random Number Generator
DongDong recently became obsessed with randomization, and random number generators is the foundation of randomization. DongDong plans to use the linear congruential method to generate a number sequence. This method requires for nonnegative integer parameters m, a, c, X0. Then, a random sequence <Xn> can be generated using the following formula:
Xn + 1 = (aXn + c) mod m
where "mod m" means to take the remainder after the left hand expression has divided m. It can be observed from this equation that the next number in a sequence will always be based off of the current number.
Sequences generated this way are very random in nature, which is why this method has been used extensively. Even randomization functions in the widely used standard libraries of C++ and Pascal employ this method.
DongDong knows that sequences produced this way are very random, but he is also impatient about wanting to know the value Xn as soon as possible. Since DongDong needs a random number that's one of 0, 1, …, g − 1, he will have to modulo the number Xn by g to get the final result. All you have to do is determine the value of Xn mod g for DongDong.
Input Format
The input consists of 6 space-separated integers m, a, c, X0, n, and g. Here, a, c, and X0 are nonnegative while m, n, g are positive.
Output Format
Output a single integer, the value of Xn mod g.
Sample Input
11 8 7 1 5 3
Sample Output
2
Explanation
The first few terms of <Xn> are:
| k | 0 | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|---|
| Xk | 1 | 4 | 6 | 0 | 7 | 8 |
Thus the answer is X5 mod g = 8 mod 3 = 2.
Constraints
| Test Case | n | m, a, c, X0 | m, a | g |
|---|---|---|---|---|
| 1 | n ≤ 100 | m, a, c, X0 ≤ 100 | m is prime | g ≤ 108 |
| 2 | n ≤ 1000 | m, a, c, X0 ≤ 1000 | m is prime | |
| 3 | n ≤ 104 | m, a, c, X0 ≤ 104 | m is prime | |
| 4 | n ≤ 104 | m, a, c, X0 ≤ 104 | m is prime | |
| 5 | n ≤ 105 | m, a, c, X0 ≤ 104 | m and a − 1 are prime | |
| 6 | n ≤ 105 | m, a, c, X0 ≤ 104 | m and a − 1 are prime | |
| 7 | n ≤ 105 | m, a, c, X0 ≤ 104 | m and a − 1 are prime | |
| 8 | n ≤ 106 | m, a, c, X0 ≤ 104 | / | |
| 9 | n ≤ 106 | m, a, c, X0 ≤ 109 | m is prime | |
| 10 | n ≤ 106 | m, a, c, X0 ≤ 109 | / | |
| 11 | n ≤ 1012 | m, a, c, X0 ≤ 109 | m is prime | |
| 12 | n ≤ 1012 | m, a, c, X0 ≤ 109 | m is prime | |
| 13 | n ≤ 1016 | m, a, c, X0 ≤ 109 | m and a − 1 are prime | |
| 14 | n ≤ 1016 | m, a, c, X0 ≤ 109 | m and a − 1 are prime | |
| 15 | n ≤ 1016 | m, a, c, X0 ≤ 109 | / | |
| 16 | n ≤ 1018 | m, a, c, X0 ≤ 109 | / | |
| 17 | n ≤ 1018 | m, a, c, X0 ≤ 109 | / | |
| 18 | n ≤ 1018 | m, a, c, X0 ≤ 1018 | m is prime | |
| 19 | n ≤ 1018 | m, a, c, X0 ≤ 1018 | m is prime | |
| 20 | n ≤ 1018 | m, a, c, X0 ≤ 1018 | / |
For all of the test cases: n, m, g ≥ 1, and a, c, X0 ≥ 0.
All Submissions
Best Solutions
Point Value: 15 (partial)
Time Limit: 1.00s
Memory Limit: 512M
Added: Aug 13, 2014
Languages Allowed:
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3
Comments (Search)
It's quiet in here...