Algoritmizace B4B33ALG
Algoritmizace

Expanze množin

Zadání

Je dáno celé nezáporné číslo x1 a tři funkce f1, f2, g: ℤ → ℤ. Posloupnost množin celých čísel H1, H2, H3, …​ definujeme takto:
H1 = {x1},
Hk+1 = Hk ∪ (({f1(x) | x ∈ Hk} ∪ {f2(x) | x ∈ Hk}) − {g(x) | x ∈ Hk}), pro k ≥ 1.

Pro daných sedm celých nezáporných čísel A1, B1, A2, B2, A3, B3, M, definujeme funkce f1, f2, g takto:
f1(x) = (A1·x + B1) mod M,
f2(x) = (A2·x + B2) mod M,
g(x) = (A3·x + B3) mod M.

Vstup

Na vstupu je jeden řádek, který obsahuje čísla x1, A1, B1, A2, B2, A3, B3, M v tomto pořadí oddělená mezerou. Všechny hodnoty na vstupu leží v rozmezí od 0 do 107, M ≠ 0.

Výstup

Na výstupu je jeden řádek s celým číslem udávajícím mohutnost množiny HM. Hodnota |HM| nepřesáhne 106.

Příklady

Příklad 1

Vstup
3 3 7 4 6 5 11 17
Výstup
12

Jednotlivé množiny Hk jsou v tomto případě
H1 = {3},
H2 = {1, 3, 16},
H3 = {1, 2, 3, 4, 10, 16},
H4 = {1, 2, 3, 4, 5, 10, 12, 13, 16},
H5 = {1, 2, 3, 4, 5, 7, 10, 12, 13, 16},
H6 = {0, 1, 2, 3, 4, 5, 7, 10, 11, 12, 13, 16},
HM = H17 = H6.

Příklad 2

Vstup
1 1 5 1 3 1 7 105
Výstup
56

Příklad 3

Vstup
12341 61132 87122 40001 62243 822217 122221 1201001
Výstup
702585

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