603 Pairs

[•wefgef]

Aici puteţi discuta despre problema Pairs.

[•girl_style]

Am citit rezolvarea de la Pairs(preONI 2008,runda 1) si nu am inteles partea asta :
"Consideram toate numerele P ce se scriu ca produs de numere prime, unde fiecare numar prim este folosit cel mult o data. Daca numarul de numere prime din descompunerea lui P este un numar impar, adunam xP la Res. Altfel, din Res scadem xP."
As fi recunoscatoare sa-mi poata explica cineva...ms anticipat

[•pauldb]

2 * 5 -> numar P
3 * 6 -> nu e numar P pentru ca 6 nu e numar prim
5 * 7 * 7 -> nu e numar P pentru ca 7 se repeta
2 * 3 * 5 -> numar pentru care X[P] trebuie adunat
5 * 11 -> numar pentru care X[P] trebuie scazut

[•andrei_blanaru]

In cazul in care exista x_p numere care se divid cu p atunci exista Combin(x_p,2) perechi de numere neprime intre ele. Problema este ca pot exista perechi de numere care au mai multi divizori comuni. Si atunci acestea vor fi numarate de mai multe ori.

Sa consideram urmatoarele numere: 15, 105, 165. Pentru p=3 vor exista 3 perechi de numere pe care le vom aduna la Res. Pentru p=5, la fel. Cand ajungem la p=15 vom scadea 3 perechi obtinand astfel rezultatul corect. 15 este produs de 2 numere prime si asta inseamna ca perechile neprime care se formeaza pentru p=15 au fost numarate o data pentru p=3 si inca o data pentru p=5. Si atunci trebuie sa le scadem.

Cand p este produs pe 3 numere prime p=a*b*c, perechile trebuie adunate iar, pentru ca au fost scazute de prea multe ori. Astfel: au fost adunate pentru p=a, p=b, p=c si scazute pentru p=a*b, p=b*c, p=a*c. Asa ca trebuie adunate iar.

Numerele p a caror descompunere in factori primi contine acelasi termen de mai multe ori nu prezinta interes pentru ca perechile de numere neprime intre ele care corespund acestor numere p au fost numarate anterior pentru acele valori p=p', unde p' contine termenii lui p luati o singura data.

Sper ca explicatia mea este corecta si suficient de clara.

[•Marius]

Daca pentru fiecare numar retii o lista cu toate numerele prime ce il divid (sunt cel mult 7 astfel de numere), atunci, cu principiul includerii si excluderii poti determina cate perechi au cmmdc > 1. Totul in O(N sqrt MAX + N * 2^{numar divizori}).

[•filipb]

? Mie imi pare mai rapid in O(MAX log MAX) decat ce ai zis tu.

[•CocoSpaima]

Daca ar putea cineva sa explice fiecare pas pe exemplul 2,3,6. Fiecare Xp, p si res (Xp, p si res cu semnificatia din solutia problemei).

[•filipb]

M = {2, 3, 6}.
X(i) = numarul de numere din M care se divid cu i ( i >= 2 )
X(2) = 2 {2 si 6 se divid cu 2}, X(3) = 2 {3 si 6 se divid cu 2}, X(4) = 0, X(5) = 0, X(6) = 1, X(7) = 0...

Res = 0
1) P = 2. 2 e numar prim, deci Res = Res + X[2](X[2]-1)/2 = 0 + 2*1/2 = 1
2) P = 3. 3 e numar prim, deci Res = Res + X[3](X[3]-1)/2 = 1 + 2*1/2 = 2
3) P = 4. 4 se scrie ca 2², deci factorul prim 2 apare la exponentul 2 si nu luam acest P in considerare
4) P = 5. 5 = 5¹. X[5] = 0, se trece la pasul urmator
5) P = 6. 6 = 2¹ * 3¹. 6 se scrie deci ca produs de numere prime, in care fiecare numar prim apare la exponentul 1. Pentru ca 6 are 2 factori primi ( deci numar par de factori ), avem Res = Res - X[6](X[6]-1)/2 = 2 - 1*0/2 = 2.

Asta inseamna ca exista 3*(3-1) / 2 - 2 = 1 pereche (x y) cu cmmdc(x, y) = 1 ( perechea e 2, 3 ).

Era o mica greseala in articol, am modificat.

[•CocoSpaima]

Mai bine acum. Multzumesc mult 

[•Marius]

? Mie imi pare mai rapid in O(MAX log MAX) decat ce ai zis tu.

E mai rapid in O(MAX log MAX). Doar ca ziceam o alternativa la solutia oficiala.
Insa, in practica a mea e de trei ori mai rapida, din cate vad din sursa pe care ai trimis-o.

[•devilkind]

Eu nush ce face filip acolo dar e destul de lent:

N * 2^nr_de_divizori - http://infoarena.ro/job_detail/109331 

[•Marius]

Ce complexitate ai tu devilkind ? O(N * 2^{numar divizori}) ? Cum asa ?

[•devilkind]

pai ptr fiecare numar vreau sa stiu cate perechi pot forma cu numerele din stanga lui. Ptr un element v[ i ] initial consider ca pot forma i-1 perechi. Apoi iau fiecare submultime de divizori primi ai acestuia si dak ea are cardinal impar adun nr[j] ( j= produsul divizoril din submultime, nr[j] - numarul de elemente din stanga lui i care se divid la j), daca cardinalul e par atunci scad, si ptr fiecare submultime mai fac si nr[j]++, iar ptr fiecare numar determin divizori lui primi uitanduma doar la numerele prime mai mici ca sqrt( x ).

[•bogdan2412]

pai atunci e O(N sqrt MAX + N * 2^numar divizori), adica ce a zis si Marius... cand N ajunge egal cu MAX, atunci ai complexitatea MAX sqrt MAX, care e mult mai nashpa decat MAX log MAX Doar pe limitele astea cand N e relativ mic fata de MAX merge bine solutia asta..

[•ionescu88]

Salut!! Iau 3 TLE si restul ok....are cineva vreo idee cum pot face mai optim?

[•Dastas]

Cum pot determina eficient numerele in a caror descompunere fiecare divizor prim apare o singura data?

Cu factorizarea fiecarui numar se ajunge la O(MAX sqrt MAX) si imi iese din timp pe aproape toate testele...

[•devilkind]

tii minte intrun vector numerele prime, si apoi cand factorizezi parcurgi numai acele numere atata timp cat prim*prim < n.

[•Dastas]

tii minte intrun vector numerele prime, si apoi cand factorizezi parcurgi numai acele numere atata timp cat prim*prim < n.

Pai asa fac, iar asta e O(MAX sqrt MAX) deoarece se parcurg toate numerele de la 2 la MAX, iar pt fiecare numar i din acestea se parcurg O(sqrt(i)) numere => O(MAX sqrt MAX) in total...
 

[•cos_min]

tii minte intrun vector numerele prime, si apoi cand factorizezi parcurgi numai acele numere atata timp cat prim*prim < n.

Pai asa fac, iar asta e O(MAX sqrt MAX) deoarece se parcurg toate numerele de la 2 la MAX, iar pt fiecare numar i din acestea se parcurg O(sqrt(i)) numere => O(MAX sqrt MAX) in total...
 

Ai grija sa te opresti din factorizare cand nu mai are rost sa cauti alt numar prim. Adica daca ai intalnit un factor cu puterea > 1 te opresti. De asemenea vezi ca ai nevoie de nr prime pana la 1000001 doar.

[•Dastas]

De ce pana la 10^6? Eu mi-am generat pana la sqrt(10^6)...
Cred ca pana la 10^6 ar lua mai mult timp generarea si nici nu vad cu ce m-ar ajuta.

Ma opresc cand gasesc un factor care apare de doua ori, dar tot iau TLE. Am incercat sa exclud si patratele perfecte din cautare si tot TLE...

Calcularea vectorului X am observat ca ia peste jumatate din timp pe testele mari. Aici nu se poate optimiza nimic?

[•astronomy]

Ce-ai intrebat tu poti sa faci inteligent tot ca la ciurul lui Erastotene si sa obtii O(MAX*logMAX).

[•cos_min]

De ce pana la 10^6? Eu mi-am generat pana la sqrt(10^6)...
Cred ca pana la 10^6 ar lua mai mult timp generarea si nici nu vad cu ce m-ar ajuta.

Ma opresc cand gasesc un factor care apare de doua ori, dar tot iau TLE. Am incercat sa exclud si patratele perfecte din cautare si tot TLE...

Calcularea vectorului X am observat ca ia peste jumatate din timp pe testele mari. Aici nu se poate optimiza nimic?

Scuze da se poate pana la sqrt(10^3), greseala mea.

[•Dastas]

Ce-ai intrebat tu poti sa faci inteligent tot ca la ciurul lui Erastotene si sa obtii O(MAX*logMAX).

Intr-adevar, a intrat in sub o secunda asa. Mersi!

[•andrici_cezar]

am si eu nevoie de cinva sa imi zica ce are programul meu am pus 55 de 1 000 000 si nu imi ia din timp si acolo imi zice ca nu gaseste fiserul dar totusi am unul oki. ma ajuta cineva ca mor de ciuda

[•marcelcodrea]

Incearca sa maresti vectorul ! Nu iti ajunge unul de 100 de elemente !
Eroarea aia apare din cauza ca accesezi o zona de memorie nedeclarata !