012 Ridicare la putere in timp logaritmic

[•filipb]

Aici puteti discuta despre problema Ridicare la putere in timp logaritmic.

[•savim]

O alta problema care seamana cu asta e "modulo".

[•filipb]

De fiecare data cand aveti o problema asemanatoare, adaugati-o chiar voi in enunt .

[•Robytzza]

se uita si cineva peste sursa mea sa-mi zica ce gresesc
LE: am pus un /2 in plus

[•pauldb]

De fiecare data cand aveti o problema asemanatoare, adaugati-o chiar voi in enunt.

Enunturile problemelor nu pot fi modificate decat de admini si de cei care le-au creat.
[Later edit: ] Sau se poate.

se uita si cineva peste sursa mea sa-mi zica ce gresesc

Nu cred ca adopti cea mai buna atitudine. In concurs nu are cine sa-ti gaseasca greselile in surse. Eventual mai uita-te cum au facut altii si poate te prinzi ce gresesti.

Off topic:
Daca iti schimbi poza, iti dau un plus.

[•Robytzza]

nu schimb poza ..ca nu am de ce  

[•sima_cotizo]

Eu am bagat matricea scrisa de Cosmin in latex. Era ceva de genul:

(x y z)
(0 1 0)
(0 0 1)

si am transformat-o in ce e acum... ideea e ca eu cred ca e gresita : daca inmultesc matricea-linie (a[k-1],a[k-2],a[k-3]) cu matricea aia nu obtin (a[k], a[k-1], a[k-2]) cum zice enuntul, dar daca inmultesc cu matricea:

x 1 0
y 0 1
z 0 0

obtin ce trebuie... asta pe hartie cel putin... gresesc?

[•Cosmin]

Inmultesti matricea A cu o coloana. Si matricea e
(x y z)
(1 0 0)
(0 1 0)

[•sima_cotizo]

Am modificat-o  ce ziceam eu e echivalent

[•domino]

Nu uita sa bagi si $ la formatarea variabilelor.

[•domino]

Am modificat un pic la explicatii. In primul rand algoritmul lui Euclid nu e o metoda mai generala de a determina inversul modular, e pur si simplu alta metoda. Poti folosi teorema lui Fermat la fel de bine si cand p nu e prim (varianta originala e ceva de genu a^phi(n) = 1 (mod n) unde cmmdc(a, n) = 1). De asemenea, matricea A era gresita. Nu e bine sa se strecoare astfel de greseli cand o problema e deja in arhiva, deoarece lumea invata din start gresit.

[•Cosmin]

Mircea chestia cu a^phi(n) = 1 mod n e o teorema diferita si se numeste teorema lui Euler. Deci era corect ca fata de ideea din mica teorema a lui Fermat, ideea din algoritmul lui Euclid extins rezolva o problema mai generala. Daca vrei explica-le si teorema lui Euler dar atunci mai trebuie sa calculezi si phi(n) (si asta ia O(sqrt(n)) timp ... ).

Matricea A nu era gresita daca inmulteai A cu o coloana nu cu o linie. Dar la inceput nu stiam cum se scrie o coloana in latex.

Am dat revert la changeurile tale, si am pus coloane in loc de linii pentru sirul a.

[•Bogdan_tmm]

Oare de ce primesc Killed by Signal sigsv (crek asa scrie) Se uita cineva si pe sursa mea?

[•sima_cotizo]

Ce-mi sare in ochi este ca ar trebui sa citesti din "lgput.in" (ala e "L" mic) ... si sa scrii in "lgput.out"

[•Bogdan_tmm]

DA  Eu crezusem ca e "i" mare  dar tot iau doar 10 p.Oricum ms.Acum nu mai am timp .Sper sa o fac de 100

[•belgun_adrian]

incearca sa folosesti ca tip de date int64 daca faci in pascal sau long long daca faci in c/c++

[•cosser]

e interesant ca functia pow() din <math> nu este eficienta

[•skyel]

functia pow() eficienta...dar nu pentru cazurile in care ai nevoie de modulo la rezultat. Mai degraba e vorba ca nu iti da rezultatul corect, si nicidecum de timp.

P.S. cu pow() poti sa calculezi si destul de multi radicali de ordin superior

[•Florian]

Din cate stiu eu, functia pow() nu are complexitate O(logB), ci O(B). Gresesc cumva? 

[•vlad_oltean]

Din cate stiu eu, functia pow() nu are complexitate O(logB), ci O(B). Gresesc cumva? 

daca

functia pow() din <math> nu este eficienta

, inseamna ca ai dreptate

[•byndrsn]

Din cate stiu eu, functia pow() nu are complexitate O(logB), ci O(B). Gresesc cumva? 

Cel mai probabil este O(B) pentru ca pow() lucreaza cu doubles (pow(double, double)).

[•domino]

Ma indoiesc ca e O(B) fiindca B e real. Din cate stiu pow(a, b) este echivalent cu exp(b*log(a)) , dar habar n-am cum e implementat exp()

[•Cosmin]

Parca functiile gen sin cos exp sqrt sunt calculate prin serii ce converg la numarul respectiv.

[•byndrsn]

Nici eu nu stiu cum este implementata exp(x). Ma gandeam ca aproximeaza mantissa folosind primii cativa termeni din Taylor series pentru e^{x - n ln(2)}, unde n este exponentul (n = floor(x / ln(2))).

[•alexthero]

Functia power din STL este implementata in timp logaritmic.