Exponențierea rapidă

Exponențierea rapidă (binary exponentiation) calculează a^n în O(log n) în loc de O(n) naiv.

E fundamentală când n e mare (10^9, 10^18) sau când calculezi a^n mod m în probleme cu numere mari.

Problema

Calculează a^n.

a = 3, n = 13
a^n = 3^13 = 1594323

Soluția naivă O(n)

long long rez = 1;
for (int i = 0; i < n; i++)
    rez = rez * a;

Pentru n = 10^18, asta înseamnă 10^18 înmulțiri - imposibil în timp util.

Ideea exponențierii rapide

Observă că:

a^(2k) = (a^k)^2

a^(2k+1) = a * (a^k)^2

Deci, dacă știm a^k, putem calcula a^(2k) sau a^(2k+1) cu o singură înmulțire în plus.

Asta înjumătățește exponentul la fiecare pas → O(log n).

Exemplu

a^13 = a^(1101 în binar)
     = a^8 * a^4 * a^1
     = a^(2^3) * a^(2^2) * a^(2^0)

Calculăm a^1, a^2, a^4, a^8, ... și le înmulțim doar pe cele pentru care bitul corespunzător din n e 1.

Varianta iterativă

long long putereRapida(long long a, long long n) {
    long long rez = 1;
    while (n > 0) {
        if (n & 1)        // daca bitul curent e 1 (sau este impar)
            rez *= a;
        a *= a;            // ridicam baza la patrat
        n >>= 1;           // shift la dreapta (împărțim la 2)
    }
    return rez;
}

Cum funcționează

Parcurgem biții lui n de la cel mai puțin semnificativ:

• a devine a, a^2, a^4, a^8, ...
• rez acumulează produsul acelora pentru care bitul din n e 1

Varianta modulară

În majoritatea problemelor competitive, vrem a^n mod m:

long long putereModulo(long long a, long long n, long long m) {
    long long rez = 1;
    a %= m;  // reducem baza de la inceput
    while (n > 0) {
        if (n & 1)
            rez = rez * a % m;
        a = a * a % m;
        n >>= 1;
    }
    return rez;
}

Doar adăugăm % m la fiecare înmulțire.

Cod complet

#include <fstream>
using namespace std;
ifstream fin("date.in");
ofstream fout("date.out");

const long long MOD = 1000000007;

long long putere(long long a, long long n, long long m) {
    long long rez = 1;
    a %= m;
    while (n > 0) {
        if (n & 1)
            rez = rez * a % m;
        a = a * a % m;
        n >>= 1;
    }
    return rez;
}

int main()
{
    long long a, n;
    fin >> a >> n;
    fout << putere(a, n, MOD);
    return 0;
}

date.in:

2 1000000000000000000

date.out:

719476260

Adică 2^(10^18) mod (10^9 + 7) = 719476260. Calculat în microsecunde.

Pas cu pas: 3^13

n = 13 = 1101 în binar.

Rezultat: 3^13 = 1594323 ✓

Varianta recursivă

long long putereRec(long long a, long long n, long long m) {
    if (n == 0) return 1;
    long long jum = putereRec(a, n / 2, m);
    long long rez = jum * jum % m;
    if (n & 1) rez = rez * a % m;
    return rez;
}

Elegantă dar folosește memorie O(log n) pentru stiva de apeluri. Iterativ e mai bine.

Aplicații

1. Inversul modular

Dacă m e prim, prin mica teoremă a lui Fermat:

a^(-1) ≡ a^(m-2) (mod m)

long long invers(long long a) {
    return putere(a, MOD - 2, MOD);
}

2. Combinări modulo

C(n, k) = n! * (k!)^(-1) * ((n-k)!)^(-1) (mod m)

Precalculăm factoriale și inversele lor, apoi fiecare C(n, k) se calculează în O(1).

3. Numărul lui Fibonacci cu matrici

F(n) poate fi calculat în O(log n) prin exponențierea matricei:

[F(n+1)]   [1 1]^n   [F(1)]
[F(n)  ] = [1 0]   * [F(0)]

4. Repetări de operații

Dacă o operație are inversă și e asociativă, poți aplica exponentierea rapidă (exemplu: rotații pe un grup de elemente, tranzacții pe arbori).

Complexitate

Pentru n = 10^18, log n ≈ 60 operații. Instant.

Greșeli frecvente

1. Overflow la a * a

int a = 1e9, m = 1e9 + 7;
int x = a * a % m; // OVERFLOW! int nu tine 10^18

long long x = (long long)a * a % m; // CORECT

Regulă: toate variabilele implicate să fie long long.

2. n nu e reducibil modulo

a^n mod m  →  nu poti reduce n mod m!

Dacă m e prim, poți folosi n mod (m-1) prin Fermat. Pentru general, nu.

3. Exponent negativ

a^(-k) = (a^(-1))^k. Dacă ai nevoie de exponent negativ, calculează mai întâi inversul modular și apoi ridică la puterea k.

4. Uitarea a %= m la început

long long putere(long long a, long long n, long long m) {
    long long rez = 1;
    // a %= m; // daca lipseste si a > m, primul a * a poate face overflow
    ...
}

Dacă a > m, poate cauza overflow în primele iterații. Mereu reduci baza inițial.

5. Confuzia & cu &&

if (n & 1)   // test de bit - CORECT pentru paritate
if (n && 1)  // test logic - GRESIT, e mereu true daca n != 0

Variantă: x^n % m pentru m non-prim

Pentru m non-prim (sau necunoscut), algoritmul de bază funcționează normal. Doar inversul modular nu merge cu Fermat - trebuie algoritmul lui Euclid extins.

Ce să reții

• Exponențiere rapidă calculează a^n în O(log n) prin descompunere binară.
• Ideea: a^(2k) = (a^k)^2, a^(2k+1) = a * (a^k)^2.
• Implementarea iterativă: parcurge biții lui n, înmulțește în rezultat bazele corespunzătoare.
• Varianta modulară: adaugă % m la fiecare înmulțire.
• Folosește long long pentru a evita overflow.
• Aplicații: invers modular (Fermat), combinări, orice grup asociativ.
• Pentru m prim: a^(-1) ≡ a^(m-2) (mod m).