• Najnowsze pytania
  • Bez odpowiedzi
  • Zadaj pytanie
  • Kategorie
  • Tagi
  • Zdobyte punkty
  • Ekipa ninja
  • IRC
  • FAQ
  • Regulamin
  • Książki warte uwagi

Szybkie potęgowanie

0 głosów
144 wizyt
pytanie zadane 7 grudnia 2020 w C i C++ przez Nie Wiem Nowicjusz (240 p.)
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ć :(
komentarz 7 grudnia 2020 przez Nie Wiem Nowicjusz (240 p.)
zapomniałem dodać, że czas na wykonanie to 0,1 sekundy, przy zakładaniu, że 10^6-10^8 to jedna sekunda
komentarz 8 grudnia 2020 przez jankustosz1 Nałogowiec (30,160 p.)
A próbowałeś chociaż to napisać? To naprawdę nie jest nic trudnego, użyj rekurencji
komentarz 8 grudnia 2020 przez Nie Wiem Nowicjusz (240 p.)
próbowałem, na większych potęgach typu 1000 już się wywala :(
komentarz 8 grudnia 2020 przez jankustosz1 Nałogowiec (30,160 p.)
Pewnie nie konwertujesz na long longa i wychodz poza zakres inta
komentarz 8 grudnia 2020 przez Nie Wiem Nowicjusz (240 p.)
już wszystko działa, dzięki za chęć pomocy :)

2 odpowiedzi

+2 głosów
odpowiedź 8 grudnia 2020 przez Eriss69 Gaduła (4,050 p.)
komentarz 8 grudnia 2020 przez Nie Wiem Nowicjusz (240 p.)
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
komentarz 8 grudnia 2020 przez Nie Wiem Nowicjusz (240 p.)
trochę pokombinowałem i działa! dzięki
komentarz 9 grudnia 2020 przez Eriss69 Gaduła (4,050 p.)
brawo :D
0 głosów
odpowiedź 8 grudnia 2020 przez TOM_CPP Pasjonat (19,260 p.)

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

 

Podobne pytania

0 głosów
1 odpowiedź 1,160 wizyt
pytanie zadane 5 czerwca 2017 w C i C++ przez Koper Początkujący (310 p.)
0 głosów
1 odpowiedź 290 wizyt
pytanie zadane 23 sierpnia 2019 w C i C++ przez believer88 Nowicjusz (230 p.)
0 głosów
2 odpowiedzi 128 wizyt
pytanie zadane 4 czerwca 2017 w C i C++ przez Krystek102 Bywalec (2,430 p.)
Porady nie od parady
Komentarze do pytań nie służą do odpowiadania, od tego jest wydzielona sekcja odpowiedzi. Funkcją komentarzy jest natomiast możliwość uzyskania dodatkowych informacji na temat samego posta.Komentarze

85,212 zapytań

134,029 odpowiedzi

297,158 komentarzy

56,309 pasjonatów

Motyw:

Akcja Pajacyk

Pajacyk od wielu lat dożywia dzieci. Pomóż klikając w zielony brzuszek na stronie. Dziękujemy! ♡

Oto dwie polecane książki warte uwagi. Pełną listę znajdziesz tutaj.

...