De ce contează?
Vrei să afli cât face 2 la puterea 10. Nu ai un buton magic, dar ai un creion: scrii 1, apoi îl dublezi — 2, 4, 8, 16... — și ții socoteala de câte ori ai dublat. După zece dublări ai răspunsul. Exact așa „ridici la putere" un calculator care nu știe decât să înmulțească: pornește de la 1 și înmulțește cu baza, iar și iar, de câte ori îi spune exponentul.
Intuiția
A ridica a la puterea n înseamnă, prin definiție, să înmulțești a cu el
însuși de n ori: a^n = a * a * ... * a. Nu ai nevoie de nimic mai deștept ca
să obții răspunsul — doar de un acumulator care reține produsul de până acum și
de o buclă care îl înmulțește cu a la fiecare pas. Imaginea mentală e un șir
recurent: fiecare termen este termenul anterior înmulțit cu baza.
Toată lecția se reduce la o singură linie repetată: p = p * a (cu % m adăugat
dacă problema cere modulo, deci p = p * a % m). Acumulatorul p pleacă de la
1 — elementul neutru la înmulțire — și după n repetări conține exact a^n.
Aplicând % m la fiecare pas, p rămâne mereu sub m și nu depășește
niciodată tipul de date.