Problem G
RNG Test

Áð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

10 3 42 42 1009

311

17 18 20 1000000000000000000 100003

41617

1 1 164 500000000000000000 1000000007

500000192