Faktorizacija 2 - Ne radi checker i Kako izbeci TLE?

Pitanja i problemi
1

https://petlja.org/BubbleBee/r/Problems/FACT2
Za bilo koji izlaz daje OK.
Bilo bi dobro kada bi neko iz komisije ili neko koje stvarno uradio ovaj zadatak mogao da pusti kod ovde.
Jedino resenje koje mi pada na pamet je O( T*M), sto ne prolazi u 1s, M je broj prostih brojeva do 10^6, a T broj primera datih u zadatku.
M < 80.000, T < 5.000

1 Like
2

@Lazar_Bojicic jel mozes pls da pogledas i oznacis zadatak?
Uzgred, zadatak nema veze sa komisijom za takmicenja, ovaj kurs je radila inicijalna BubbleBee ekipa.

1 Like
3

Primetimo da ukoliko broj nije prost dovoljno je da proverimo prvih M+k prostih brojeva jer ako je deljiv sa neki prostim brojem van ovog skupa onda je deljiv sa jos nekim vecim od 10^6 pa je broj veci od 10^12. Ovo nam daje skup kandidata koji ce imati oko 80000 clanova. Pretpostavimo da ga mozemo napisati pomocu l prostih brojeva na rastojanjima k. Neka se najmanji prost broj u tom rastavljanju nalazi na poziciji x (u sortiranom skupu prvih M+k prostih brojeva), tu poziciju mozemo naci binarnom pretragom ako ona postoji (postojanje takodje proveravamo binarnom pretragom). Ukoliko pozicija x ne postoji uvecamo l za 1. Posto broj koji je manji od 10^12 moze imati najvise 10 razlicitih prostih delilaca dovoljno je proveriti one vrednosti l manje ili jednake od 10 i ako ne postoji resenje ni za jedno l onda je broj prost, jer se garantuje da neko rastavljanje broja postoji. Ovo nam daje konacnu slozenost O(L*(L*log(M+k))) gde je L najveci moguci broj razlicitih prostih delilaca n.

1 Like
4

E to, hvala ti :smiley:
…