Blum Blum Shub ternární strom
Mezi známé a používané generátory pseudnáhodných čísel patří také generátor nazývaný podle svých objevitelů Blum Blum Shub generátor. Jeho výhodou je veliká jednoduchost a snadná zapamatovatelnost formule, pomocí níž se pseudonáhodná čísla generují. Na základě tohoto generátoru vytvoříme kořenový ternární strom, jehož vlastnosti budeme zkoumat v této úloze.Pro dané celé kladné číslo M definujeme funkci BBS.
BBS: ℤ → ℤ: BBS(x, M) = (x×x) mod M.
Pro čtveřici celých nezáporných čísel (x, L, H, M) definujeme rekurzivně ternární strom, který označíme BBS3(x, L, H, M), takto:
1. Pro H ≤ x je BBS3(x, L, H, M) strom obsahující pouze kořen a tím je číslo x.
2. Pro L ≤ x < H je BBS3(x, L, H, M) strom s kořenem x, přičemž tento kořen má jediný podstrom a tím je strom BBS3(BBS(x, M), L, H, M).
3. Pro x < L je BBS3(x, L, H, M) strom s kořenem x, přičemž tento kořen má tři podstromy BBS3(BBS(x, M)+1, L, H, M), BBS3(BBS(x, M)+2, L, H, M), BBS3(BBS(x, M)+3, L, H, M).
(Termínem podstrom daného uzlu označujeme strom, jehož kořen je bezprostředním potomkem daného uzlu.)
Vstup
Na vstupu je jeden řádek s pěticí celých kladných čísel x, L, H, M, D oddělených navzájem jednou mezerou.Hodnoty x, L, H, M, nepřevýší 109, hodnota D nepřevýší 106.
Výstup
Na výstupu je jeden řádek s jediným celým číslem představujícím celkový počet uzlů v hloubce menší než D ve stromu BBS3(x, L, H, M). (Platí, že kořen stromu má hloubku 0.)V této uloze můžeme předpokládat, že nalezený počet uzlů nepřesáhne 107.
Příklad 1
Vstup:13 5 15 21 4Výstup:
14
Příklad 2
Vstup:13 5 15 21 8Výstup:
26
Příklad 3
Vstup:19 20 130 143 1000000Výstup:
2000002