Blum Blum Shub ternární strom

Zadání

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ýší 10⁹, hodnota D nepřevýší 10⁶.

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 10⁷.

Příklady

Příklad 1

Vstup

13 5 15 21 4

Výstup

Příklad 2

Vstup

13 5 15 21 8

Výstup

Příklad 3

Vstup

19 20 130 143 1000000

Výstup

Veřejná data

Veřejná data k úloze jsou k dispozici. Veřejná data jsou uložena také v odevzdávacím systému a při každém odevzdání/spuštění úlohy dostává řešitel kompletní výstup na stdout a stderr ze svého programu pro každý soubor veřejných dat.

Veřejná data