Editorial for Slepi brojevi


Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.

Submitting an official solution before solving the problem yourself is a bannable offence.

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


Comments

There are no comments at the moment.