Exponentiere rapida

Ridicare la putere in timp logaritmic

== include(page="template/taskheader" task_id="lgput") ==
 
Dandu-se doua numere naturale $N$ si {$P$}, se cere sa se calculeze restul impartirii lui $N^P^$ la $1999999973$.
 
h2. Date de intrare
 
Fisierul de intrare $lgput.in$ va contine 2 numere $N$ si $P$.
 
h2. Date de iesire
 
In fisierul de iesire $lgput.out$ va fi scris un singur numar reprezentand restul impartirii lui $N^P^$ la $1999999973$.
 
h2. Restrictii
 
* $2 ≤ N, P ≤ 2^32^$
 
h2. Exemplu
 
table(example). |_. lgput.in |_. lgput.out |
| 2 4
| 16
|
 
 
h2. Indicatii de rezolvare
 
O solutie directa este cea prin inmultiri repetate. Aceasta solutie are complexitatea $O(P)$ si obtine 30 de puncte.
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 matrice 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 rapida 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 <tex> \left( \begin{array}{ccc}
a[k] \\
a[k - 1] \\
a[k - 2]\end{array} \right)</tex> fiind dat de inmultirea matricii $A$: <tex> \left( \begin{array}{ccc}
x & y & z \\
1 & 0 & 0 \\
0 & 1 & 0 \end{array} \right)</tex> cu vectorul <tex> \left( \begin{array}{ccc}
a[k - 1] \\
a[k - 2] \\
a[k - 3]\end{array} \right)</tex>
 
Si atunci pentru a determina $a[k] modulo n$ rapid, putem folosi ridicarea la putere a matricii $A$.
 
h2. Probleme similare
 
* 'Iepuri':problema/iepuri
* 'Modulo':problema/modulo
* ' Nice Patterns Strike Back':http://acm.sgu.ru/problem.php?contest=0&problem=197
 
== include(page="template/taskfooter" task_id="lgput") ==
 
 

Scrie aici despre problema/lgput

task: lgput

public

2787