Atenţie! Aceasta este o versiune veche a paginii, scrisă la 2008-02-28 20:36:22.
Revizia anterioară Revizia următoare
Revizia anterioară Revizia următoare
| Fişierul intrare/ieşire: | lgput.in, lgput.out | Sursă | ad-hoc |
| Autor | Arhiva Educationala | Adăugată de |  Tudorica Constantin Alexandru •tudalex |
| Timp execuţie pe test | 0.025 sec | Limită de memorie | 20480 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Poti vedea testele pentru aceasta problema accesand atasamentele.Vezi solutiile trimise | Statistici
Ridicare la putere in timp logaritmic
Se cere sa se calculeze restul impartirii lui NP la 1999999973.
Date de intrare
Fisierul de intrare lgput.in va contine 2 numere N si P.
Date de iesire
In fisierul de iesire lgput.out va fi scris un singur numar reprezentand restul impartirii lui NP la 1999999973.
Restrictii
- 2 ≤ N, P ≤ 232.
Exemplu
| lgput.in | lgput.out |
|---|---|
| 2 4 | 16 |
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, O(logP) wikipedia. Algoritmul se aplica si la matrici si polinoame.
Sursa de 100 de puncte se gaseste aici.
Probleme similare
Trebuie sa te autentifici pentru a trimite solutii. Click aici
