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) ~.