Problema Ridicare A^b In Timp Logaritmic

[Kid Koder]

Enunt

Se dau doua numere A si B. Se cere sa se determine numarul X = A^B% 1999999973, unde x % y reprezinta restul impartirii lui x la y.

 

Restrictii:

 

A, B - pozitive

A, B < 1.000.001

 

Exemplu:

 

date.in

2 5

date.out

32

Explicatii: 2⁵ % 1999999973. = 32 % 1999999973 = 32.

 

Indicatii de rezolvare:

 

Problema se poate rezolva in mai multe moduri:

1) Prin inmultiri directe, solutie cu complexitate O(B) --> solutie ineficienta din punct de vedere al timpului de executie.

2) Solutia de ridicare in timp logaritmic, solutie cu complexitate O(log₂ B) --> solutie de punctaj maxim.

 

Cod:

long long rise(long long A, long long B) {
   if(B == 0) return 1; // un numar ridicat la puterea 0 da rezultatul 1.

   long long x = rise(A, B / 2) % MOD; // pentru a nu calcula de doua ori rise(A, B / 2), il calculam o singura data in x

   if(B % 2 == 0) return (x * x) % MOD; // daca puterea B este una para, atunci inmultim x cu el insusi deoarece A^(B/2) * A^(B/2) = A^B;
   else return (((x * x) % MOD) * A) % MOD; // A^(B/2) * A^(B/2) != A^B deoarece ne ramane un A pe dinafara, B-ul fiind numar impar.

/*
 Solutia are complexitate O(log2 B) deoarece numerele:
A^0, A^1, A^2, A^4, A^8, etc... sunt calculate O SINGURA DATA.
Ca sa intelegeti mai usor, imaginati-va B ca fiind scris in baza 2, iar fiecare bit x reprezinta A^X din descompunerea sa.
*/
}

Problema de exersare: lgput -> infoarena

 

Daca aveti nelamuriri legat de partea de teorie/practica, lasati un reply in acest topic.

Nota: Codul NU a fost compilat. Daca gasiti vreo eroare de compilare/sintaxa, lasati reply/PM.

@Kid Koder 2015