@milosh
To je kao rešenje za zadatak http://www.spoj.com/problems/PRIME1/
Tj. generisu se svi prosti brojevi do 10^6, i onda se koriste ti brojevi za ispitivanje brojeva do 10^12
1 Like
Nisam na to mislio, inače može i do 10^18 (i više)
Šta je bilo, prpa? 
1 Like
Iskreno i dalje mislim da mi je 4. tacan, mogu da posaljem kod ali me je strah da mi ne nadjete test gde ne radi
Koliko sam primetio, rešenje za drugi je prvi prost broj manji od Ai (ili kako se već zvaše), tj. broj sa najmanjom trivijalnošću u intervalu [2, n] je prvi prost broj <= n, tako da sam bio razočaran kad sam video koliko su mala ograničenja.
Ograničenja su takva da bi prolazili i neki malo sporiji algoritmi, ipak je 2. zadatak
Razmisli o tome sta se desava ako je cena za potez mnogo velika, a cena jednog dzokera bas mala.
Ja sam uradio DP trivijalnost(x) = (trivijalnost(najvecidelilac) * delilac + broj)/broj valjda ce raditi za sve
Četvrti je klasičan https://en.wikipedia.org/wiki/Hirschberg's_algorithm, samo je još potrebno da se implementiraju poeni.
Jasno, samo šteta da je zadatak sa toliko različitih rešenja tek drugi (inače mi se sviđa bez obzira što je jednostavan).
Meni to ne deluje tačno
2 Likes
btw kako dokazati da je resenje prethodni prost broj. Nikako nisam mogao da dokazem
bruteforcovao sam da bih dokazao
trivijalnost(10) = 1.8
trivijalnost(5) = 3 edit: trivijalnost(5) = 1.2
(trivijalnost(5)*5 + 10) /10 = 2.5 edit: = 1.6
Neka je x slozen broj a p neki njegov prost delilac. Onda se lako pokazuje da je trivijalnost od p manja od trivijalnosti od x. Dakle dovoljno je gledati samo proste brojeve. A najtrivijalniji je onaj koji je najveci.
2 Likes
Ali trivijalnost od 5 je 1.2
36 ti je kontraprimer
nebitno nebitno nebitno
Moja greska, delio sam sa brojem delioca slucajno, svakako primer radi
I ja mislim da sam negde pogresio, kad unesem do 20k, bude 19999 a trebalo bi 19997 T_T