Mohutnost množiny

Jsou dána čtyři kladná celá čísla a, N, b, M. Množiny A(a, N), B(b, M) a C(a, N, b, M) jsou definovány takto:
A(a, N) = {a1, a2, a3, ..., aN}, a1 = a, ai = ai−1+1 pro 1 < i ≤ N,
B(b, M) = {b1, b2, b3, ..., bM}, b1 = b, bj = bj−1+1 pro 1 < j ≤ M,
C(a, N, b, M) = { (ai, aj) ∈ A(a, N) ×A(a, N) | 1 ≤ i < j ≤ N & ∃ y ∈ B(b, M): aiaj = y }.

Vypočtěte mohutnost množiny C(a, N, b, M) pro dané hodnoty a, N, b, M.

Vstup

Na vstupu je textový soubor obsahující jediný řádek. Na řádku jsou uvedena čísla a, N, b, M v tomto pořadí oddělená navzájem jednou mezerou. Platí
a < 230, N < 230, b < 260, M < 260. Data jsou zadána korektně, není nutno je kontrolovat.

Výstup

Na výstupu je jediný řádek s jedním celým číslem představujícím mohutnost množiny C(a, N, b, M). Pokud je tato množina prázdná, je její mohutnost 0. Data jsou volena tak, že hodnota výstupu nikdy nepřevýší 260. Na vstupu i na výstupu jsou vždy pouze celá čísla bez desetinné tečky, bez exponentu a bez jakýchkoli dalších formátových specifikací.

Poznámka

Výpočet lze poměrně jednoduše provést s asymptotickou složitostí Θ(N), výpočet s větší asymptotickou složitostí (např. pomocí "hrubé síly") bude pravděpodobně příliš pomalý.

Příklad 1

Vstup:
2 2 5 5
Výstup:
1

Příklad 2

Vstup:
2 5 4 15
Výstup:
7

Příklad 3

Vstup:
1 10 91 1000
Výstup:
0

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