Să se scrie o funcție RECURSIVA IN C++ numită putere care primește 3 numere naturale a,b,c și calculează restul împărțirii lui [tex]a^{b}[/tex] la c.

***Funcția trebuie să se numească putere.
***Funcția trebuie să primească 3 parametri de tip int și să returneze un int care să stocheze numărul cerut

Restricții
***1 ≤ a ≤ 100
***2 ≤ c ≤ 1000
***0 ≤ b ≤ 1 000 000 000

Exemplu
putere(3, 6, 100) va returna 29.

Cum să calculezi eficient și corect!

Dacă încerci să îl ridici pe a la puterea b prin înmulțiri repetate, vei vedea că programul tău va fi lent și vei primi limită de timp depășită când trimiți.

Poți să calculezi [tex]a^{b}[/tex] mai eficient folosindu-te de următoarea proprietate: [tex]a^{b}[/tex] = [tex]a^{b/2}[/tex] ∗ [tex]a^{b/2}[/tex] în cazul în care b este par, altfel [tex]a^{b}[/tex] = a ∗ [tex]a^{b-1}[/tex] . Acest lucru este ușor de demonstrat dacă ne bazăm pe faptul că [tex]a^{b}[/tex] ∗ [tex]a^{c}[/tex] = [tex]a^{b+c}[/tex] .

Atenție! Deoarece numerele cresc foarte mult atunci când le înmulțim, trebuie să ai grijă ca valoarea lor să poată fi memorată într-o variabilă de tip int.

Pentru a face acest lucru poți să te bazezi pe faptul că a ∗ b și RA ∗ RB au același rest prin împărțirea la c , unde prin RA am notat restul lui a la împărțirea cu c și prin RB restul la împărțirea cu c al lui b.

DORESC SERIOZITATE! LA CEA MAI BUNA SOLUTIE PUN COROANA!!!