Problem je zadatak Faraon, A2, sa okružnog takmičenja 2016. godine. Primarna ideja mi je bila da predstavim brojeve P i Q u kanonskom obliku i samo izračunam apsolutnu razliku stepena činilaca (koji su sačuvani u okviru jednog hash array-a) izmedju ta dva broja. Međutim, TLE se baš i ne slaže sa mojom idejom.
Koji je najoptimalniji način da se reši ovaj zadatak?
Mislim da je ideja u suštini na mestu, i da je ovde problem u detaljima implementacije. Par stvari:
Nema razloga da čuvaš stepene kao hash array (i da trošiš vreme na pravljenje strukture, a zatim na prolaženje kroz nju), umesto toga možeš da “paralelno” faktorišeš oba broja i u isto vreme računaš razlike.
Kako tražiš proste faktore? Pošto treba faktorisati puno brojeva, ima smisla generisati sve proste brojeve do \sqrt{N} na početku i onda testirati samo njih (a ne, na primer, sve neparne brojeve).
