Nu obții 100 de puncte sau ai nelămuriri în privința problemelor? Scrie-mi pe Instagram.
Ai găsit o greșeală, vrei să raportezi un utilizator sau vrei să comunici altceva? Folosește formularul de contact.
Vrei să ne transmiți o părere despre platformă? Folosește formularul de feedback.
Folosește următoarele shortcuturi pentru a naviga mai ușor pe platformă.
Meniu shortcuturi | ? |
Căutare probleme sau utilizatori | / |
Navigare printre rezultatele căutării | ↑, ↓ |
Meniu de contact și feedback | CTRL + Shift + F |
Ieșire din meniuri | Esc |
Setări editor | CTRL + Shift + S |
Schimbare stil editor | CTRL + Shift + E |
Șabloane de cod | CTRL + Shift + 1/2/3 |
Golire editor | CTRL + Shift + 4 |
Ridicarea la putere este o operație bineștiută, valoarea an
fiind egală cu:
Algoritmul de determinare a ridicării la putere este una ușor de intuit, având complexitatea O(n) liniară:
int rasp = 1;
for(int i = 1; i <= n; i++) {
rasp = rasp * a;
}
cout << a << "^" << n << " = " << rasp;
Mai precis, pentru a calcula operația an
ne trebuie n
operații de înmulțire… Cum putem optimiza algoritmul?
O metodă mai eficientă de a ridica la putere este ridicarea la putere în timp logaritmic, numită și exponențierea rapidă. Complexitatea acestui algoritm este O(log2 n)
. Această complexitate este incredibil de mică — spre exemplu, pentru a ridica un număr la puterea 1.000.000.000
(un miliard), facem aproximativ 30
de operații de înmulțire, în loc de un miliard cât ar fi luat cu metoda anterioară.
Algoritmul de ridicare la putere în timp logaritmic se bazează pe următoarea observație:
Cu această observație, putem calcula 220
astfel:
220 = (210)2
, deoarece n = 20
este par;210 = (25)2
, deoarece n = 10
este par;25 = 2 * (22)2
, deoarece n = 5
este impar;22 = (21)2
, deoarece n = 2
este par;21 = 2 * (20)2
, deoarece n = 1
este impar;20 = 1
.Observăm că în loc să facem 20
de înmulțiri, efectuăm doar 6
.
Implementarea recursivă folosește exact observația de mai sus:
int ridicare(int a, int n) {
if(n == 0)
return 1;
if(n % 2 == 1) {
int next = ridicare(a, (n - 1) / 2);
return a * (next * next);
} else {
int next = ridicare(a, n / 2);
return next * next;
}
}
Implementarea iterativă diferă un pic, însă se bazează pe aceeași idee. Să reprezentăm exponentul n
ca sumă de puteri de 2
. Spre exemplu, pentru n = 20
, avem suma n = 4 + 16
. Prin urmare, operația an = a20 = a(4 + 16) = a4 * a16 = (a1)0 * (a2)0 * (a4)1 * (a8)1 * (a16)1
, unde exponenții de 0
și de 1
este reprezentarea binară a lui n = 20
(10100
). Cu această idee, vom lua cifrele exponentului n
în baza 2
, de la ultima cifră către prima. Dacă cifra curentă este 1
, atunci înmulțim răspunsul cu baza a
. La fiecare pas, vom ridica baza a
la pătrat.
Iată implementarea în C++:
int ridicare(int a, int n) {
int rasp = 1;
while(n > 0) {
if(n % 2 == 1)
rasp = rasp * a;
a = a * a;
n /= 2;
}
return rasp;
}
Moca dorește să posteze pe Pbinfo a
probleme de dificultate b
. Durata postării celor a probleme de dificultate b
este restul împărțirii lui ab
la 1999999973
. Ajutați-l pe Moca să calculeze durata postării celor a
probleme de dificultate b
. Pentru enunțul complet și testarea codului poți vizita această pagină.
Exemplu: Pentru a = 2
și b = 4
, avem rezultatul 24 = 16
.
Rezolvare: Deoarece b
poate atinge valori mai mari de patru miliarde, rezolvarea problemei constă în aplicarea ridicării la putere în timp logaritmic. Observăm că rezultatul operației poate depăși cu mult orice tip de date (int
, long long
), astfel că după fiecare operație, trebuie să aplicăm restul împărțirii la 1999999973
. Cum 1999999973
este un număr prim, rezultatul nu va atinge valoarea 0
.
//Rezolvarea problemei #2398 Moka de pe PbInfo
//Explicații: https://infoas.ro
//Enunț: https://www.pbinfo.ro/probleme/2398/moka
#include <fstream>
using namespace std;
ifstream fin("moka.in");
ofstream fout("moka.out");
long long a, b;
long long ridicare(long long a, long long n) {
long long rasp = 1;
a = a % 1999999973; //În cazul în care baza depășește
//Restul operațiilor sunt identice, doar că cu modulo 1999999973
while(n > 0) {
if(n % 2 == 1)
rasp = rasp * a % 1999999973;
a = a * a % 1999999973;
n /= 2;
}
return rasp;
}
int main()
{
fin >> a >> b;
fout << ridicare(a, b);
return 0;
}
Dându-se două numere naturale N
și P
, se cere să se calculeze restul împărțirii lui NP
la 1999999973
. Pentru enunțul complet al problemei și testarea soluțiilor vizitează această pagină.
Exemplu: Pentru numerele N = 2
și P = 5
, soluția este 25 = 32
.
Rezolvare: Observăm că problema este identică cu cea de dinainte (inclusiv operația modulo
). Astfel, doar numele fișierelor se schimbă:
//Rezolvarea problemei lgput de pe InfoArena
//Explicații: https://infoas.ro
//Enunț: https://www.infoarena.ro/problema/lgput
#include <fstream>
using namespace std;
ifstream fin("lgput.in");
ofstream fout("lgput.out");
long long a, b;
long long ridicare(long long a, long long n) {
long long rasp = 1;
a = a % 1999999973; //În cazul în care baza depășește
//Restul operațiilor sunt identice, doar că cu modulo 1999999973
while(n > 0) {
if(n % 2 == 1)
rasp = rasp * a % 1999999973;
a = a * a % 1999999973;
n /= 2;
}
return rasp;
}
int main()
{
fin >> a >> b;
fout << ridicare(a, b);
return 0;
}
# | Problemă | Dificultate |
---|---|---|
4. | Ridicare la putere in timp logaritmic | Medie (4 |
644. | Roboti | Medie (4 |