NOI '12 P1 - Random Number Generator - DMOJ: Modern Online Judge

NOI '12 P1 - Random Number Generator

View as PDF

Submit solution

All submissions

Best submissions

Points: 15 (partial)

Time limit: 0.6s

Memory limit: 512M

Problem type

National Olympiad in Informatics, China, 2012

DongDong recently became obsessed with randomization, and random number generators are the foundation of randomization. DongDong plans to use the linear congruential method to generate a number sequence. This method requires nonnegative integer parameters $m$ ~m~, $a$ ~a~, $c$ ~c~, $X_0$ ~X_0~. Then, a random sequence $\langle X_n \rangle$ ~\langle X_n \rangle~ can be generated using the following formula:

$\displaystyle X_{n+1} = (aX_n + c) \bmod m$

where " $\bmod m$ ~\bmod m~" means to take the remainder after the left hand expression has divided $m$ ~m~. It can be observed from this equation that the next number in a sequence will always be based on 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 $X_n$ ~X_n~ as soon as possible. Since DongDong needs a random number that's one of $0, 1, \dots, g-1$ ~0, 1, \dots, g-1~, he will have to modulo the number $X_n$ ~X_n~ by $g$ ~g~ to get the final result. All you have to do is determine the value of $X_n \bmod g$ ~X_n \bmod g~ for DongDong.

Input Specification

The input consists of $6$ ~6~ space-separated integers $m$ ~m~, $a$ ~a~, $c$ ~c~, $X_0$ ~X_0~, $n$ ~n~, and $g$ ~g~. Here, $a$ ~a~, $c$ ~c~, and $X_0$ ~X_0~ are nonnegative while $m$ ~m~, $n$ ~n~, $g$ ~g~ are positive.

Output Specification

Output a single integer, the value of $X_n \bmod g$ ~X_n \bmod g~.

Sample Input

11 8 7 1 5 3

Sample Output

Explanation

The first few terms of $\langle X_n \rangle$ ~\langle X_n \rangle~ are:

$k$ ~k~	$0$ ~0~	$1$ ~1~	$2$ ~2~	$3$ ~3~	$4$ ~4~	$5$ ~5~
$X_k$ ~X_k~	$1$ ~1~	$4$ ~4~	$6$ ~6~	$0$ ~0~	$7$ ~7~	$8$ ~8~

Thus the answer is $X_5 \bmod g = 8 \bmod 3 = 2$ ~X_5 \bmod g = 8 \bmod 3 = 2~.

Constraints

Test Case	$n$ ~n~	$m, a, c, X_0$ ~m, a, c, X_0~	$m, a$ ~m, a~	$g$ ~g~
$1$ ~1~	$n \le 100$ ~n \le 100~	$m, a, c, X_0 \le 100$ ~m, a, c, X_0 \le 100~	$m$ ~m~ is prime	$g \le 10^8$ ~g \le 10^8~
$2$ ~2~	$n \le 1\,000$ ~n \le 1\,000~	$m, a, c, X_0 \le 1\,000$ ~m, a, c, X_0 \le 1\,000~	$m$ ~m~ is prime
$3$ ~3~	$n \le 10^4$ ~n \le 10^4~	$m, a, c, X_0 \le 10^4$ ~m, a, c, X_0 \le 10^4~	$m$ ~m~ is prime
$4$ ~4~	$n \le 10^4$ ~n \le 10^4~	$m, a, c, X_0 \le 10^4$ ~m, a, c, X_0 \le 10^4~	$m$ ~m~ is prime
$5$ ~5~	$n \le 10^5$ ~n \le 10^5~	$m, a, c, X_0 \le 10^4$ ~m, a, c, X_0 \le 10^4~	$m$ ~m~ and $a-1$ ~a-1~ are prime
$6$ ~6~	$n \le 10^5$ ~n \le 10^5~	$m, a, c, X_0 \le 10^4$ ~m, a, c, X_0 \le 10^4~	$m$ ~m~ and $a-1$ ~a-1~ are prime
$7$ ~7~	$n \le 10^5$ ~n \le 10^5~	$m, a, c, X_0 \le 10^4$ ~m, a, c, X_0 \le 10^4~	$m$ ~m~ and $a-1$ ~a-1~ are prime
$8$ ~8~	$n \le 10^6$ ~n \le 10^6~	$m, a, c, X_0 \le 10^4$ ~m, a, c, X_0 \le 10^4~	/
$9$ ~9~	$n \le 10^6$ ~n \le 10^6~	$m, a, c, X_0 \le 10^9$ ~m, a, c, X_0 \le 10^9~	$m$ ~m~ is prime
$10$ ~10~	$n \le 10^6$ ~n \le 10^6~	$m, a, c, X_0 \le 10^9$ ~m, a, c, X_0 \le 10^9~	/
$11$ ~11~	$n \le 10^{12}$ ~n \le 10^{12}~	$m, a, c, X_0 \le 10^9$ ~m, a, c, X_0 \le 10^9~	$m$ ~m~ is prime
$12$ ~12~	$n \le 10^{12}$ ~n \le 10^{12}~	$m, a, c, X_0 \le 10^9$ ~m, a, c, X_0 \le 10^9~	$m$ ~m~ is prime
$13$ ~13~	$n \le 10^{16}$ ~n \le 10^{16}~	$m, a, c, X_0 \le 10^9$ ~m, a, c, X_0 \le 10^9~	$m$ ~m~ and $a-1$ ~a-1~ are prime
$14$ ~14~	$n \le 10^{16}$ ~n \le 10^{16}~	$m, a, c, X_0 \le 10^9$ ~m, a, c, X_0 \le 10^9~	$m$ ~m~ and $a-1$ ~a-1~ are prime
$15$ ~15~	$n \le 10^{16}$ ~n \le 10^{16}~	$m, a, c, X_0 \le 10^9$ ~m, a, c, X_0 \le 10^9~	/
$16$ ~16~	$n \le 10^{18}$ ~n \le 10^{18}~	$m, a, c, X_0 \le 10^9$ ~m, a, c, X_0 \le 10^9~	/
$17$ ~17~	$n \le 10^{18}$ ~n \le 10^{18}~	$m, a, c, X_0 \le 10^9$ ~m, a, c, X_0 \le 10^9~	/
$18$ ~18~	$n \le 10^{18}$ ~n \le 10^{18}~	$m, a, c, X_0 \le 10^{18}$ ~m, a, c, X_0 \le 10^{18}~	$m$ ~m~ is prime
$19$ ~19~	$n \le 10^{18}$ ~n \le 10^{18}~	$m, a, c, X_0 \le 10^{18}$ ~m, a, c, X_0 \le 10^{18}~	$m$ ~m~ is prime
$20$ ~20~	$n \le 10^{18}$ ~n \le 10^{18}~	$m, a, c, X_0 \le 10^{18}$ ~m, a, c, X_0 \le 10^{18}~	/

For all of the test cases: $n, m, g \ge 1$ ~n, m, g \ge 1~ and $a, c, X_0 \ge 0$ ~a, c, X_0 \ge 0~.

Problem translated to English by Alex.

Comments

There are no comments at the moment.