Diferente pentru problema/lgput intre reviziile #18 si #39

Nu exista diferente intre titluri.

Diferente intre continut:

== include(page="template/taskheader" task_id="lgput") ==
Se cere sa se calculeze restul impartirii lui $N^P^$ la $1999999973$.
Dandu-se doua numere naturale $N$ si {$P$}, se cere sa se calculeze restul impartirii lui $N^P^$ la $1999999973$.
h2. Date de intrare
h2. Restrictii
* $2 ≤ N, P ≤ 2^32^$.
* $2 ≤ N, P ≤ 2^32^$
h2. Exemplu
h2. Indicatii de rezolvare
O solutie este cea directa de a ridica numsrul la putere, aceasta are o complexitate de $O(P)$  si obtine 30 de puncte.
O alta solutie este cea de a ridica la putere in timp logaritmic si are o complexitate de $O(logP)$, descrierea o gasiti aici pe "wikipedia":http://en.wikipedia.org/wiki/Exponentiation_by_squaring. Algoritmul se aplica si la matrici si polinoame.
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") ==
 

Nu exista diferente intre securitate.

Diferente intre topic forum:

 
2787