Ridicare la putere

De ce contează?

Ca să afli 2¹⁰, înmulțești 2 cu el însuși de zece ori: 2, 4, 8, 16... până la 1024. E simplu și direct — exact ca atunci când dublezi o sumă din nou și din nou. Dar dacă exponentul e uriaș, vei vrea ceva mai isteț.

Ce înseamnă ridicarea la putere

aⁿ (a la puterea n) este produsul lui a cu el însuși de n ori:

aⁿ = a · a · ... · a (de n ori), iar a⁰ = 1

Exemple: 2³ = 8, 5² = 25, 3⁴ = 81.

Algoritm pas cu pas: 3⁴

`i`	înmulțim cu 3	`rezultat`
start	—	1
1	1·3	3
2	3·3	9
3	9·3	27
4	27·3	81

Implementare C++

#include <iostream>
using namespace std;

long long putere(int a, int n) {
    long long rezultat = 1;          // a^0 = 1
    for (int i = 1; i <= n; i++) {
        rezultat *= a;               // inmultim de n ori
    }
    return rezultat;
}

int main() {
    cout << putere(3, 4) << "\n";    // 81
    cout << putere(2, 10) << "\n";   // 1024
    return 0;
}

Observația-cheie

Acumulatorul pornește de la 1, nu de la a. Astfel cazul n = 0 iese corect (bucla nu rulează, rezultatul rămâne 1 = a⁰), iar pentru n ≥ 1 faci exact n înmulțiri.

Varianta modulo

Puterile cresc exploziv. Când problema cere aⁿ % M, aplică modulo după fiecare înmulțire:

long long putereMod(long long a, int n, long long M) {
    long long rezultat = 1;
    a %= M;                          // reducem baza de la inceput
    for (int i = 1; i <= n; i++) {
        rezultat = (rezultat * a) % M;
    }
    return rezultat;
}

Limita metodei

Această metodă face n înmulțiri — O(n). Pentru n = 10⁹, înseamnă un miliard de pași, prea lent. Soluția e exponențierea rapidă (lecția următoare), care face doar ~30 de pași folosind dublarea exponentului.

Complexitate

Metodă	Timp	Spațiu
înmulțiri repetate	O(n)	O(1)
exponențiere rapidă	O(log n)	O(1)

Greșeli frecvente

Capcane reale la ridicarea la putere:

Overflow rapid: 2⁶³ depășește long long. Fără modulo, puterile mari se sparg aproape imediat — folosește long long și/sau modulo.
Inițializare cu 0 sau cu a: cu 0 rezultatul e mereu 0; cu a strici cazul n = 0. Pornește de la 1.
Modulo doar la final: valoarea s-a spart deja pe parcurs. Aplică % M după fiecare pas.
O(n) pentru n mare: corect, dar depășește timpul. Treci la exponențiere rapidă.

De reținut

aⁿ = înmulțești 1 cu a de n ori; a⁰ = 1, deci pornește de la 1.
Pentru aⁿ % M, aplică modulo după fiecare înmulțire.
Metoda e O(n) — pentru n mare folosește exponențierea rapidă, O(log n).