Contact și feedback

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.

Shortcuturi

Folosește următoarele shortcuturi pentru a naviga mai ușor pe platformă.

Generale

Meniu shortcuturi?
Căutare probleme sau utilizatori/
Navigare printre rezultatele căutării↑, ↓
Meniu de contact și feedbackCTRL + Shift + F
Ieșire din meniuriEsc

Editor probleme

Setări editorCTRL + Shift + S
Schimbare stil editorCTRL + Shift + E
Șabloane de codCTRL + Shift + 1/2/3
Golire editorCTRL + Shift + 4

Ridicarea la putere în timp logaritmic în C++. Exponențiere rapidă

Ridicarea la putere este o operație bineștiută, valoarea an fiind egală cu:

https://i.ibb.co/BjjHMML/temp2-min.png

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?

Cum putem ridica la putere într-un mod eficient

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ă.

Cum funcționează exponențierea rapidă

Algoritmul de ridicare la putere în timp logaritmic se bazează pe următoarea observație:

https://i.ibb.co/kQxttMz/temp3-min.png

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.

Implementare recursivă a exponențierii rapide

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ă a exponențierii rapide

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;
}

Probleme rezolvate

#2398 Moka (PbInfo)

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;
}

Ridicare la putere in timp logaritmic: lgput (InfoArena)

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;
}

Probleme propuse

# Problemă Dificultate
4. Ridicare la putere in timp logaritmic Medie (4 )
644. Roboti Medie (4 )
747. Pandemia Grea (8 )

Alte resurse sau bibliografie

Obține medalia mult dorită. Devino As la olimpiadă.

Curs complet de olimpiadă, pregătit de olimpici de la Oxford și TU Delft.

Cuprinsul lecției

Se încarcă…

Citește și

Operații cu numere mari în C++ - Toate funcțiile explicateInversarea unui vector în C++Generarea șirului Fibonacci generalizat în C++Al N-lea termen dintr-o progresie aritmeticăAlgoritm recursiv pentru căutare binară (clasa a X-a)Cum să afișezi partea întreagă a unui număr real în C++Indicatorul lui Euler al numerelor de la 1 la N (Folosind ciurul lui Eratostene)De ce cer unele probleme răspunsul modulo 666013 sau modulo 1.000.000.007?Ce înseamnă variabilă globală și locală în C++?Inversarea unui șir de caractere în C++Aria și circumferința unui cerc în C++Oglinditul unui număr în C++Al N-lea termen Fibonacci în C++Ce este o variabilă unsigned în C++?Verifică dacă un număr este par sau impar fără modulo în C++Funcții predefinite în C++ (matematice, șiruri de caractere)Șiruri de caractere în C++. Tot ce trebuie să știiCel mai frecvent element dintr-un șir în C++Vectorii în C++: declarare și parcurgereTransformarea unui număr din baza 2 în baza 10 în C++Maximul și minimul a două valori în C++Cifrele unui număr. Prelucrarea cifrelor unui număr în C++Instrucțiunea continue (structuri repetitive)Vectori de frecvență (de apariții) în C++Cum să citești și să afișezi în fișiere în C++Ridicarea la putere în timp logaritmic în C++. Exponențiere rapidăTipuri de date în C++: numere întregi, reale, caractere și alteleNumărul combinărilor în C++ (formula combinărilor)Rădăcina cubică a unui număr în C++ (cube root)Radicalul unui număr în C++ (rădăcina pătrată)Interschimbarea a două variabile în C++ (3 metode)Aria unui triunghi folosind coordonatele acestora în C++Maximul și minimul a trei valori în C++Numărul minim de peroane pentru o gară în C++Maximul și minimul unui vector în C++Citirea și afișarea matricelor în C++CMMDC recursiv a două numere naturale în C++Suma numerelor naturale dintr-un interval dat în C++Numere triunghiulare. Verificarea unui număr triunghiularIndicatorul lui Euler în C++Numărul de cifre ale factorialului unui numărAl N-lea termen dintr-o progresie geometricăVerificare dacă șir de caractere este palindrom în C++Verifică dacă o literă este mică sau mare în C++Verifică dacă un bit de pe o anumită poziție este 1 sau 0 în C++Vectorii în C++: citire și afișareVerifică dacă un număr dat este o putere de 2 în C++Află secolul unui an citit de la tastatură în C++Interclasarea a doi vectori în C++Oglinditul recursiv al unui număr în C++Numărul aranjamentelor în C++ (formula aranjamentelor)Valoarea absolută (modulul) unui număr în C++Mediana unui șir de valori în C++Instrucțiunea while (structuri repetitive)Instrucțiunea break (structuri repetitive)Cum să calculezi instant 2 la puterea N în C++Materia pentru olimpiada de informatică - tot ce trebuie să știiCea mai lungă secvență de elemente crescătoare în C++Ce înseamnă endl în C++?Aplicații cu ciurul lui Eratostene în C++: suma divizorilor, numărul divizorilorCiurul lui Eratostene în C++Transformarea unei litere mari în literă mică în C++Numărul de divizori primi ai unui număr în C++Verificare număr prim în C++ (Clasa a IX-a)Comentarii în C++Verifică dacă un caracter este cifră în C++CMMMC a două numere în C++ (cel mai mic multiplu comun)Transformarea unei litere mici în literă mare în C++Afișarea divizorilor primi ai unui număr în C++Căutare binară în C++Calculul combinărilor de n luate câte k (nCk) în C++Aflarea sumei primelor N sume GaussTransformarea unui număr din baza 10 în baza 2 în C++Factorialul unui număr în C++Numărul de divizori al numerelor de la 1 la N (Folosind ciurul lui Eratostene)Matrice pătratice în C++. Diagonala principală și secundarăAfișarea elementelor unui vector recursiv în C++Tipul struct în C++. Ce sunt structurile de date neomogeneDo while vs while în C++ - Care e diferența?Distanța dintre două puncte în C++Cel mai semnificativ bit în C++Cifra maximă și minimă a unui număr în C++Cel mai mic/mare divizor prim al numerelor de la 1 la N (Folosind ciurul lui Eratostene)Funcții în C++. Ce sunt subprogrameleCodul ASCII (tabel complet)Pointer în C++. Variabile de tipul char * (char steluță)Maximul și minimul a n valori în C++Instrucțiunea for (structuri repetitive)Tutorial instalare CodeBlocks (ușor) - Introducere în informatică C++Cifra de control a unui numărCitește un șir de caractere cu spații în C++Ce este o funcție void în C++?Verifică dacă un caracter este literă în C++Complexitatea unui algoritm (timp și spațiu) în C++Șirul lui Fibonacci în C++Verifică dacă trei puncte sunt coliniare C++Sortare crescătoare recursivă în C++ - Merge sort și Bubble sortStructuri repetitive (while, do while, for, etc)Copiuțe: Cifrele unui numărDivide et Impera (metodă de programare C++)Bordarea unei matrice în C++Verifică dacă o literă este vocală în C++Cifra maximă a unui număr recursiv în C++Numărul permutărilor în C++ (formula permutărilor)Prima cifră a unui număr în C++Cel mai puțin semnificativ bit în C++Matrice Fibonacci - al n-lea termen Fibonacci în timp logaritmicNumărul de divizori al unui număr în C++Recursivitate în C++Numărul de apariții al unui număr într-un vector în C++Verifică dacă un număr aparține șirului Fibonacci în C++Suma 1 + 2 + 3 + ... + N în C++Combinatorică în C++: permutări, aranjamente, combinări și alteleMatrice în C++. Declararea și parcurgerea tablourilor bidimensionaleCel mai mic număr cu suma cifrelor N în C++Suma divizorilor numerelor de la 1 la N (Folosind ciurul lui Eratostene)Suma elementelor unui vector recursiv în C++Cel mai mare divizor comun (CMMDC) a două numere în C++Instrucțiunea de decizie în C++: if, else, switch, caseCâte numere naturale sunt într-un interval dat? (C++)Verificarea unui an bisect în C++Instrucțiunea do while (structuri repetitive)Suma divizorilor unui număr în C++Verificare dacă un număr este palindrom în C++

© Drepturi de autor

Echipa InfoAs își rezervă drepturile de autor pentru conținutul acestei pagini. Copierea conținutului fără acordul scris expres al InfoAs reprezintă o încălcare a Legii 8/1996 și va fi tratată ca atare.

Trimite lecția

Toată lecția

Doar videoclipul pe YouTube

Informatica devine ușoară cu InfoAs

Intră în cont