127 Resturi

[ditzone]

Aici puteţi discuta despre problema Resturi.

[•junior]

Am facut problema asta folosind teorema chineza (algebra mai avansata un pic, se gaseste si prin CLR, daca e cineva interesat). Si tot iau WA... Nu stiu exact de ce, dar la folosesc la un moment dat produsul acelor N numere prime date. E posibil ca asta sa depaseasca long long si sa fie nevoie de numere mari?

[•greco]

Pai da, cam e nevoie de numere mari.

[•junior]

Dar solutia voastra, "oficiala", foloseste teorema chineza? Sau e ceva mai simplu la care eu nu m-am gandit?

[•greco]

Nu prea ai cum s-o faci fara teorema chineza a resturilor.

[•junior]

La un moment dat, pt a calcula x^(-1) modulo y, folosesc algoritmul extins al lui euclid. Pot evita asta facand altceva? Ca-i destul de urat sa faci asta cu numere mari...

[•greco]

Da, poti evita gcd extins, dar nu te astepta sa-ti spunem exact cum se face, pentru ca am strica tot farmecul.  

[•junior]

Ok, mersi pt raspunsuri. Nici nu voiam sa-mi spui exact cum, e mai misto sa cauti singur. Da macar sa stii ca ceea ce cauti exista.

[nivan]

Am cautat teorema chineza ca sa o studiez... doar ca nu am gasit-o... imi puteti spune shi mie unde sa o gasesc. Shtiu ca s-a scris mai sus ca se gaseste in CLR, dar in alta parte.

[•domino]

Am cautat teorema chineza ca sa o studiez... doar ca nu am gasit-o... imi puteti spune shi mie unde sa o gasesc. Shtiu ca s-a scris mai sus ca se gaseste in CLR, dar in alta parte.

Ai incercat pe Google? Cauta "Chinese Remainder Theorem", m-as mira sa nu gasesti...  

[nivan]

mersi...... eu am cautat cu "teroema chineza" shi daia nu am gasit. Chiar am gasit un site cu mai multe (unele le shtiu deja) dar o sa-mi faca placere sa le studiez pe restul.

[•svalentin]

mai este cunoscuta si ca "lema" (in loc de "teorema")

[•junior]

Da, e cunoscuta ca si ca "lema".

[•Zeus]

multumim pt. completare junior ...

[•junior]

Imi cer scuze pt ca ceea ce am scris e redundant. Din neatentie, am crezut ca ce a zis svalentin e o intrebare, nu o afirmatie!
Scuza-ma!

[VladS]

Cam cate teste sunt ?

[ditzone]

cam ... 125

[•pauldb]

Cat va da pe testul asta?

Cod:

30
797 796
809 808
811 810
821 820
823 822
827 826
829 828
839 838
853 852
857 856
859 858
863 862
877 876
881 880
883 882
887 886
907 906
911 910
919 918
929 928
937 936
941 940
947 946
953 952
967 966
971 970
977 976
983 982
991 990
997 996

[•Darth_Niculus]

 Am implementat Teorema Chineza pe vectori si imi merge pe toate testele care mi-au trecut prin cap.

Test   Timp executie   Memorie folosita   Mesaj   Punctaj
1   1165ms   212kb   Incorect   0
Punctaj total:   0
Evaluare completa

Asa ca am ajuns la concluzia ca am alocat vectorii cam mici... asa ca i-am mai marit, dar acuma....

Test   Timp executie   Memorie folosita   Mesaj   Punctaj
1   2036ms   352kb   Time limit exceeded.   0
Punctaj total:   0
Evaluare completa

Poa sa-mi dea si mie cineva un test mai la limita (cineva care a rezolvat problema).....  de exemplu m-ar interesa rezultatul la testul postat de mai sus.

[•pauldb]

Am rezolvat problema pana la urma. Atata imi da pe testul de mai sus:

Cod:

33333269224461507932571420138931620019566440619831828603983139578148469309747572433179016

[•Darth_Niculus]

Ms.
Exact atat imi da si mie. 

Cod:

33333269224461507932571420138931620019566440619831828603983139578148469309747572433179016
33333269224461507932571420138931620019566440619831828603983139578148469309747572433179016

---------------------
[Later Edited] Gata am luat 100.... nu tratam tipurile de cazuri cand toate resturile sunt 0.

[•dcarbunescu]

e ceva de castigat daca fac problema asta? sau e doar asa pentru ca sa pierd timpul si sa ma incred ca am rezolvato? conduce la vreo concluzie generala?

[•dornescuvlad]

e ceva de castigat daca fac problema asta? sau e doar asa pentru ca sa pierd timpul si sa ma incred ca am rezolvato? conduce la vreo concluzie generala?

Te rog frumos n-o rezolva.Increde-te ca ai rezolvat-o , n-ai nimic de invatat din ea.

[•dcarbunescu]

e ceva de castigat daca fac problema asta? sau e doar asa pentru ca sa pierd timpul si sa ma incred ca am rezolvato? conduce la vreo concluzie generala?

Te rog frumos n-o rezolva.Increde-te ca ai rezolvat-o , n-ai nimic de invatat din ea.

Bune idei! Vad ca stii si sa scrii romaneste! ) Mai da-mi o idee ca nici de asta nu ma prind: cum faci de poti sa muncesti atat? Inteleg ca muncesti foarte mult fara sa iti pui problema daca ajungi la ceva... Conduce la ceva general? - intrebarea e fireasca! asta e prima intrebare la care trebuie sa ( iti) raspunzi!