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

Poveste si cerinta...

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$ ...

Fisierul de intrare $lgput.in$ va contine 2 numere $N$ si $P$.

h2. Date de iesire

In fisierul de iesire $lgput.out$ ...

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 |

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.

| 2 4
| 16

|

h3. Explicatie
 
...

h2. Indicatii de rezolvare

Un articol despre metoda de exponentiere rapida il gasiti pe "wikipedia":http://en.wikipedia.org/wiki/Exponentiation_by_squaring
 
*Comentarii Cosmin:* Se aplica si la matrici si polinoame, nu uita problema iepuri.

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") ==

2787