infoarena

Aici puteti discuta despre problema Mins (http://infoarena.ro/problema/mins).

Problema a fost adaugata de Vlad Gavrila. Mai multe detalii la Extinde arhiva (http://infoarena.ro/implica-te/extinde-arhiva).

Ar merge bagat si numarul problemei in titlul topicului :).

Am rezolvat problema de 70 de puncte. Am TLE. Vreau sa stiu daca e buna ideea. Folosesc acelasi lucru ca la problema "Frac" - principiul includerii si excluderii. Asadar, am ceva de genul:


phi( i , max ) intoarce numarul de numere prime cu i si mai mici decat max. Initial, pentru toate numerele de la 1 la min calculez factorii primi si ii retin (folosind ciurul lui Erathostene). Avandu-i retinuti, aplic functia phi (exact ca la "frac"). Ceva idei de optimizare? [ in caz de aceasta este solutia buna ] Multumesc.

nu trebuia sa fie c si d maxim 5000? :angry:
la lot asa era

Ba in mod normal da. Dar aici a fost pusa cu limita mai mare ca sa bage lumea in n*log(n). Inveti mai multe in felul acesta. Practic nu e chiar aceeasi problema ca la lot.

Bafta multa.

Dani daca nu sunt prea discret  :D
Eu am de gand sa iau toate numerele prime pana la min (c,d) si sa fac un pinex ..
adica ..
rez= c*d - (min(c,d)/primul numar prim ) - .. + (mind(c,d)/(primul numar prim*al doilea)) .. si tot asa : )

cred ca nu e optim  :peacefingers:
dar nu vad alta solutie.
macar niste indicii de rezolvare va rog ?  :weightlift:

scuze  :shock: mergea prost netul de asta am postat de 2 ori :( nu stiam ca s-a postat prima data  :x si nu gasesc butonul de erase post  :fool:

Pai da asta nu e back ce zici tu? :shock:
Gandestete ce reprezinta dreptele alea si incearca sa te gandesti cum poti aplica ciurul.

Bafta multa.