O alta solutie este cea de a ridica la putere in timp logaritmic si are o complexitatea $O(log{~2~}P)$. Descrierea acestui procedeu se gaseste pe "wikipedia":http://en.wikipedia.org/wiki/Exponentiation_by_squaring. Algoritmul se poate aplica si la matrici si polinoame.
Sursa de 100 de puncte se gaseste 'aici':job_detail/145518?action=view-source.

h3. Utilizari
 
Pentru determinarea inversul numarului x modulo un numar prim p: teorema mica a lui fermat ne spune ca x^(p-1) modulo p = 1. De aici avem ca inversul lui x este x^(p-2) pe care il putem calcula rapid folosind exponentiere rapida. O cale mai generala de a determina inversul unui numar x modulo un numar n, unde n nu este neaparat prim, ar fi folosirea algoritmului lui Euclid extins.
 
Alta tip de probleme unde exponentierea rapide ne este utila ar fi determinarea rapida a valorii modulo n a unui element a[k] unde a este un sir definit printr-o recurenta liniara.
 
De exemplu daca sirul a[k] = x a[k - 1] + y a[k - 2] + z a[k - 3], atunci putem defini vectorul (a[k], a[k - 1] , a[k - 2]) fiind dat de inmultirea vectorului (a[k - 1], a[k - 2], a[k - 3) cu matricea:
(x y z)
(0 1 0)
(0 0 1)
Si atunci pentru a determina a[k] modulo n rapid, putem folosi ridicarea la putere a matricii A.
 

h2. Probleme similare
* 'Iepuri':problema/iepuri

* ' Nice Patterns Strike Back':http://acm.sgu.ru/problem.php?contest=0&problem=197

== include(page="template/taskfooter" task_id="lgput") ==

public

task: lgput