Expanze množin
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říklad 1
Vstup:3 3 7 4 6 5 11 17Výstup:
12Jednotlivé 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 105Výstup:
56
Příklad 3
Vstup:12341 61132 87122 40001 62243 822217 122221 1201001Výstup:
702585
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.