Analiza

Primetimo da, u svim potproblemima, možemo na početku izdvojiti sve slepe brojeve - proveru da li je neki broj slep možemo uraditi u složenosti $O(\log B)$, tako da možemo izdvojiti sve takve u $\mathcal{O}((B - A)\log B)$, što je dovoljno brzo.

Potproblem 1

Primetimo da možemo da probamo sve parove slepih brojeva (ima ih najviše $(B - A) ^ 2$ (gruba granica)), i videti koji od tih parova je klep, proverom da li $K$ deli njihov proizvod, u složenosti $\mathcal{O}((B - A) ^ 2)$

Potproblem 2

Zapravo, nas samo interesuju ostaci svih slepih brojeva pri deljenju sa $K$ - samo od ostataka pri deljenju dva broja nekim brojem zavisi i ostatak proizvoda. Dakle, možemo imati brojač koliko postoji slepih brojeva sa svakim ostatkom, i u $\mathcal{O}(K^2)$ izračunati koliko ima klepih parova.

Potproblemi 3 i 4

Neka je $z$ broj slepih brojeva deljivih sa $K$. Posmatrajmo sve ostale slepe brojeve. Ukoliko posmatramo neki broj $x$, neka je $t = gcd(x, k)$. Par $(x, y)$ će biti klep ukoliko važi $\frac{k}{t} \mid y$ - dakle, kada tražimo sve brojeve koji formiraju klep par sa brojem $x$, treba nam broj brojeva deljivih sa nekim brojem. To možemo lako uraditi prolaskom kroz niz slepih brojeva (tj. njihovih ostataka pri deljenju sa $K$) - kada naiđemo na broj $x$, dodamo $\mathrm{count}[K / gcd(x, K)]$ na rešenje, i uvećamo $\mathrm{count}$ svakog delioca broja $x$ za 1. Ovo rešenje radi u složenosti $\mathcal{O}(\mathrm{brSlepih} \cdot \sqrt{K})$, što je sigurno dovoljno brzo, jer ne postoji ulaz za koji je broj slepih brojeva veći od 50000. Na ovo dobijeno rešenje treba dodati $z \choose 2$, kao i $z \cdot (\mathrm{brSlepih} - z)$.