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

Dandu-se doua numere naturale N si P, se cere sa se calculeze restul impartirii lui N^P 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 N^P la 1999999973.

Restrictii

• 2 ≤ N, P ≤ 2³²

Exemplu

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₂P). Descrierea acestui procedeu se gaseste pe wikipedia. Algoritmul se poate aplica si la matrici si polinoame.
Sursa de 100 de puncte se gaseste aici.

Probleme similare

• Iepuri

Cum se trimit solutii?