Hide

Problem G
RNG Test

Languages en is
/problems/rngtest/file/statement/is/img-0001.jpg
Áður fyrr voru teningar notaðir til að framleiða prófunargögn

Eins og vanalega fyrir Forritunarkeppni Framhaldsskólanna þarf að semja alveg gífurlegt magn af prófunargögnum til að prófa allar lausnir á. Þar sem ekki er raunhæft að skrifa öll gögnin handvirkt beitir KFFÍ (Keppnisforritunarfélag Íslands) slembitalnaframleiðendum (e. random number generators). Þar sem stjórn félagsins er mjög tortryggin er útfærslunum sem fylgja forritunar- málunum ekki treyst. Því var Atla úthlutað það verkefni að búa til línulegan slembitalnaframleiðanda. Þar sem Atli svaf hins vegar yfir sig eins og vanalega þarf einhver annar að redda málunum, þ.e.a.s. þú (eins og vanalega).

Línulegur slembitalnaframleiðandi er skilgreindur útfrá þremur heiltölum $a$, $b$, $x_0$ og látum þá $f(x) = (ax + b)\ \% \ m$. Prósentumerkið táknar módulus, og þýðir það að útkoman er reiknuð módulus $m$. Þ.e.a.s. við tökum afganginn af niðurstöðunni þegar henni er deilt með tölunni $m$.

Til að fá $n$-tu slembitöluna er $f$ beitt $n$ sinnum á upphafsstakið $x_0$. Þetta þýðir að núllta talan er $x_0$, fyrsta er $f(x_0)$, næsta er $f(f(x_0))$ o.s.frv.

Inntak

Eina línan í inntakinu inniheldur fimm heiltölur $a$, $b$, $x_0$, $n$ og $m$ eins og lýst er að ofan. Heiltölurnar eru ekki neikvæðar, og $m$ er alltaf jákvæð.

Úttak

Skrifa skal út $n$-tu slembitöluna sem línulegi slembitalnaframleiðandinn framleiðir.

Stigagjöf

Hópur

Stig

Takmarkanir

1

40

$a = 10, b = 3, m = 10^3 + 9, x_0 \leq 10^9, 1 \leq n \leq 10^6$

2

20

$m = 10^5 + 3, a, b, x_0 \leq 10^9, 1 \leq n \leq 10^{18}$

3

20

$m = 10^9 + 7, a, b, x_0 \leq 10^9, 1 \leq n \leq 10^{18}$

4

20

$a, b, x_0, m \leq 10^9 + 7, 1 \leq n \leq 10^{18}$

Sample Input 1 Sample Output 1
10 3 42 42 1009
311
Sample Input 2 Sample Output 2
17 18 20 1000000000000000000 100003
41617
Sample Input 3 Sample Output 3
1 1 164 500000000000000000 1000000007
500000192