Random Number Generator
Time limit2sMemory limit128 MB
Given a linear congruential generator with huge parameters up to 10^18, compute the n-th term modulo m and then modulo g using fast exponentiation.
- Level
Medium6 of 10
- Topics
- Math, Recursion, Matrix, Number theory
- Solved
- No attempts yet
Problem
Hongjun became interested in random sampling while studying statistics. He wants to generate random numbers from a sequence defined by a linear recurrence.
The sequence is determined by nonnegative integers m, a, c, and X0. The sequence X_n is defined as follows.
X_{n+1} = (aX_n + c) mod m
Here, A mod m means the remainder when A is divided by m.
The final random number is the remainder when X_n is divided by a positive integer g. Therefore, the generated random number is an integer from 0 to g-1, inclusive.
Given the values, write a program that computes X_n mod g.
Input
The first line contains six integers m, a, c, X0, n, and g in that order.
m, a, c, X0, and n are at most 10^18, and g is at most 10^8. The values a, c, and X0 are nonnegative integers, while m, n, and g are positive integers.
Output
Print the value of X_n mod g on the first line.
Hint
For the first public test case, the generated sequence X_n is as follows.
Thus, X_5 mod g = 8 mod 3 = 2.