Zadatak Faraon, okružno A2 2016


#1

Pitanje ili opis problema

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?

Link ka zadatku ili odgovarajućoj stranici

https://petlja.org/biblioteka/r/Problems/2016-okruzno-ss-faraon

Zahvaljujem unapred!


#2

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

#3

Problem uspešno rešen! Paralelno faktorisanje oba broja umesto hash array-a je dosta pomoglo. Hvala puno! :smiley: