|
Titlul: 1015 Xp Scris de: Stefan Istrate din Aprilie 11, 2010, 10:59:37 Aici puteti discuta despre problema Xp (http://infoarena.ro/problema/xp).
Titlul: Răspuns: 1015 Xp Scris de: Petru Trimbitas din Noiembrie 22, 2010, 17:28:40 Exista vreo proprietate pt (a/b) %p ?
Titlul: Răspuns: 1015 Xp Scris de: Paul-Dan Baltescu din Noiembrie 22, 2010, 18:18:48 Citeste aici (http://infoarena.ro/problema/inversmodular).
Titlul: Răspuns: 1015 Xp Scris de: Pripoae Teodor Anton din Noiembrie 22, 2010, 18:32:26 Se face si fara invers modular, in o(n).
Titlul: Răspuns: 1015 Xp Scris de: Petru Trimbitas din Noiembrie 22, 2010, 18:53:17 Multumesc mult :D
Ma intereseaza ceva fara invers modular(daca exista) Titlul: Răspuns: 1015 Xp Scris de: Pripoae Teodor Anton din Noiembrie 22, 2010, 20:49:26 Imparti in bucati de sqrt.
Titlul: Răspuns: 1015 Xp Scris de: Petru Trimbitas din Noiembrie 26, 2010, 16:00:21 Am citit solutia oficiala si nu spune nimic despre invers modular. Poate cineva sa descrie solutia cu invers modular? :peacefingers:
Titlul: Răspuns: 1015 Xp Scris de: Adrian Budau din Noiembrie 27, 2010, 22:59:52 Nu stiu daca chiar vrei sa afli solutia cu invers modulari. Asta e cea care am implementat-o in timpul olimpiadei si am luat 80 nu 100.
Cred totusi ca se poate obtine si 100 daca e optimizata asa ca hai sa-ti explic: Descompui numarul Q in factori primi Q=p1^q1 * p2^q2 * ..... *pk^qk Orice numar val[ i ] din sir poate fi impartit in xval[ i ] si yval[ i ] astfel incat xval[ i ] * yval[ i ] = val[ i ] si xval[ i ] are factori primi numai din multimea {p1,p2,....,pk} si yval[ i ] factori primi care nu apartin aceastei multimi. Daca notam cu P produsul val[1] * val[2] * .... * val[n], cu xP produsul xval[1] * xval[2] * ... * xval[n] si tot la fel yP din yval[1] s.a.m.d, atunci P = xP * yP Pentru a putea calcula prod[ i ] se observa ca in loc sa calculam P/val[ i ] putem calcula (xP/xval[ i ]) * (yP/yval[ i ]) (modulo Q). yp si yval[ i ] necontinand factori primi comuni cu Q sunt prime cu Q si deci putem aplica invers modular pe ele. Calculam inversul modular a lui yval[ i ] si il inmultim cu yP. Asa obtinem o parte din prod[ i ]. Pentru a obtine a xP/xval[ i ] putem putem face o precalculare. Observam ca k (numarul de factori primi din descompunerae lui Q) e relativ mic <=20. Aflam pentru fiecare valoare la ce putere se afla in xP(sa o notam cu zk). Asta se face la prima parcurgere a sirului cand se calculeaza si yP. Observam ca p1^z1 * p2^z2 * ... * pk^zk = xP Dupa ce aflam aceste valori se poate calcula o matrice calc in care calc[ i ][ j ] reprezinta pi^(zi-j). j<=30 (evident modulo Q). Avand aceste valori calculate putem afla pentru orice xval[ i ] cat face xP/xval[ i ]. Il descompunem pe xval[ i ]= p1 ^ q1' * p2 ^q2' * ... * pk^qk'. Atunci xP/xval[ i ] va fi egal cu produsul elementelor calc[ i ][ qi' ] pentru i de la 1 la k. Asa se formeaza solutia: 1) La prima parcurgere se descompune fiecare val in xval si yval si se calculeaza zi (pentru i de la k) si yP; 2) Se calculeaza matricea calc. (asta se face usor prin exponentiere rapida pana la zi-30( pentru i de la 1 la k) si inmultind cu pi pana se ajunge la zi cu exponentul. 2) La a doua parcurgere se descompun iar numerele val in xval si yval(pentru ca evident ele nu se pot mentine in memorie). Se calculeaza xP/xval[ i ] dupa procedeul descris mai sus si yP/yval[ i ] folosind invers modulare. Se inmultesc cele 2 astfel obtinandu-se prod[ i ] care se XOR-eaza cu raspunsul . Later Edit: Complexitatea Worst Case este O(n*log2(val_max) ) unde val_max in situatia de fata este 1.000.000.000. Pe cazul mediu se comporta mult mai bine, un O(n) cu constanta 8 din cate cred, voi incerca sa calculez si sa pun aici. Titlul: Răspuns: 1015 Xp Scris de: Petru Trimbitas din Noiembrie 29, 2010, 09:26:10 Ms mult :D
Titlul: Răspuns: 1015 Xp Scris de: Mihai-Alexandru Dusmanu din Aprilie 14, 2011, 12:01:08 A reusit cineva sa ia 100 pe acesta problema cu divide et impera??? Eu am tot incercat diverse optimizari si nu reusesc sa intru in timp pe ultimele 5 teste :-?
Titlul: Răspuns: 1015 Xp Scris de: Mihai Calancea din Aprilie 14, 2011, 14:00:03 Ma indoiesc ca se poate, am incercat si eu de cateva ori. Mergea foarte greu pe teste mari si l-am rugat intr-o seara pe Dragos Rotaru, cel care a pus problema in arhiva, sa mareasca pentru cateva minute limita la 20 de secunde ca sa vad de curiozitate cat i-ar lua executia pe infoarena.
http://infoarena.ro/job_detail/493324 Deci slabe sanse. Eu pana la urma am bagat varianta in sqrt(n) memorie :) Titlul: Răspuns: 1015 Xp Scris de: Mihai-Alexandru Dusmanu din Aprilie 14, 2011, 14:12:35 Multumesc mult pt raspunsul rapid... Ma mir cu de ia asa de mult timp... Mie imi intra in < 6 secunde pe toate testele de la ONI ( Celeron la 1.8 GHz si 2 GB de RAM)...
O sa incerc si solutia de sqrt(n) :D Titlul: Răspuns: 1015 Xp Scris de: Simoiu Robert din Iulie 04, 2011, 21:17:49 Vai doamne ce horror e problema asta, am reusit sa iau 100 cu divide et impera :yahoo: http://infoarena.ro/job_detail/601094.
Titlul: Răspuns: 1015 Xp Scris de: Dan H Alexandru din Martie 05, 2012, 19:02:09 Poate cineva sa imi explice solutia cu invers modular sau sa imi trimita/posteze sursa ? Am facut si eu una cu invers modular , insa intra doar pt primele 5 teste :-s
Multumesc anticipat :ok: Titlul: Răspuns: 1015 Xp Scris de: Oncescu Costin din Mai 16, 2012, 22:31:23 Imi poate spune si mie cineva ce e gresit in sursa mea de nu prinde nici un test?Pe primul exemplu am urmarit cu watch-ul si imi merge ca la carte.
Cod: void divide(unsigned long long i,unsigned long long j,unsigned long long ai,unsigned long long bi,unsigned long long prod) Foloseste tag-ul code cand postezi cod pe forum |