Szybkie potęgowanie

Question

Mam zadanie, w którym muszę podnieść liczbę 2 nawet do potęgi 10^9. Wynik podać modulo 10^9+7.

Znalazłem ten filmik: https://www.youtube.com/watch?v=uGPCF41t5gM&ab_channel=filmyoig

Chętnie bym z tego skorzystał, ale nie do końca wiem jak to zaimplementować :(

Comments

zapomniałem dodać, że czas na wykonanie to 0,1 sekundy, przy zakładaniu, że 10^6-10^8 to jedna sekunda

---

A próbowałeś chociaż to napisać? To naprawdę nie jest nic trudnego, użyj rekurencji

---

próbowałem, na większych potęgach typu 1000 już się wywala :(

---

Pewnie nie konwertujesz na long longa i wychodz poza zakres inta

---

już wszystko działa, dzięki za chęć pomocy :)

Answer 1

http://www.algorytm.edu.pl/algorytmy-maturalne/potegowanie-szybkie.html

Comments

około 60ej potęgi się wysypuje, nie do końca wiem gdzie mógłbym wstawić modulo w tej funkcji, w zaden sposob nie dziala

---

trochę pokombinowałem i działa! dzięki

---

brawo :D

Answer 2

Czas rzędu O(log(n))

#include <iostream>

using namespace std;

using ull = unsigned long long;
const int MODULO {519};

ull power2modulo( ull number )
{
    ull result {1};
    ull power {2};

    while( number > 0 )
    {
        if( number&1 ) result = result*power % MODULO;
        power = power*power % MODULO;
        number >>= 1;
    }
    return result;
}

int main()
{
    cout << power2modulo(1000000000) << endl;
}