Question

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 $a^{b}$ 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 $a^{b}$ mai eficient folosindu-te de următoarea proprietate: $a^{b}$ = $a^{b/2}$ ∗ $a^{b/2}$ în cazul în care b este par, altfel $a^{b}$ = a ∗ $a^{b-1}$ . Acest lucru este ușor de demonstrat dacă ne bazăm pe faptul că $a^{b}$ ∗ $a^{c}$ = $a^{b+c}$ .

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!!!

Answer 1

void putere(unsingned long long int a, unsingned long long int b, unsingned long long int c)  {  

   unsigned long long int x;

   if (b==0)  cout<<0<<endl;

   else {

       if (b%2==0) x=putere(a, b/2)*putere(a, b/2);

       else  x=a*power(a, b/2)*power(a, b/2);

   }

   cout<<x%c;

}