5853. Majątek Billa

[bunker96]

Witam,
Próbuję rozwiązać zadanie z tej strony http://pl.spoj.com/problems/MWP2_2B/. Niby wszystko ładnie pięknie rozwiązuje, jednak sędzia w rezultacie zwraca "błąd wykonania(SIGSEGV)" a w kolumnie mem mam 11M. Czy ten błąd spowodowany jest przekroczeniem pamięci? Jak mogę rozwiązać ten problem?
----------------Zaliczone----------------

[tycjan]

Dla danych testowych niewątpliwie zadziała, ale mowy nie ma, że zadziała dla takich danych 10000000^1000000 mod 9999, A testy mają przedział > d (1 ≤ u, s ≤ 10^6, 1 ≤ d ≤ 10000). Twój algorytm to "naiwnie" szybkie potęgowanie modularne, tu trzeba użyć innego ("ultra") szybkiego potęgowania modularnego. 11 M masz i SIGSEGV bo rekurencja, zawala pamięć szczególnie przy tak dużych danych > 10000000^1000000 mod 9999, zanim policzy co trzeba reszta "wisi" w pamięci.

[bunker96]

Ehh wszystkie algorytmy, które znajduje to ten sam który tutaj zastosowałem z tą różnicą że używane są operatory bitowe. Czy rozbicie liczby na potęgi 2 i potęgowanie tego będzie szybsze?

[tycjan]

Zdecydowanie szybsze jest rozbicie s na postać binarną można zejść nawet do O(log s), jak potęgujesz np. iteracyjnie to musisz wykonać "s" mnożeń, ale zauważ że jak rozłożysz "s" na liczbę binarną to tak naprawde, wykonasz tylko tyle mnożeń ile jest bitów o wartości 1, czyli w praktyce dużo mniej.
Bardziej wyczerpujące źródło na temat szybkiego potęgowania modularnego -> http://www.algorytm.org/algorytmy-arytmetyczne/szybkie-potegowanie-modularne.html

[narbej]

Może źle szukasz? Tak naprawdę, nie chodzi tu o szybkie potęgowanie modularne, tylko o szybkie potęgowanie. Algorytm szybkiego potęgowania jest iteracyjny a nie rekurencyjny. Jak znajdziesz już opis takiego algorytmu [szybkie potęgowanie], to już samodzielnie "włóż" do niego w odpowiednich miejscach działanie modulo. Dostaniesz wtedy właśnie szybkie potęgowanie modularne.

[joniren]

Zaimplementowałem “modularne potęgowanie przez podnoszenie do kwadratu”:
https://pastebin.com/g8GcQ5Zd (link wygaśnie po 24h)

Algorytm jest ok, ale widzę, że byli szybsi , więc zastanawiam się, co zrobić, żeby ich dogonić. Czy implementować Montgomery reduction czy inny który przyspieszy mnożenie potęg, czy w ogóle przerzucić się na inny algorytm. Nie jestem też pewien, czy zoptymalizowałem ten algorytm, który napisałem, więc jeśli macie jakieś uwagi, to rzucajcie nimi we mnie.

[j4rooo]

Niestety szybsze czasy mają cwaniaki, którzy używają szybszych funkcji wczytywania i wypisywania

Albo tak jak ja nie przejmuj się czasem w zadaniu. Tylko bierz się za następne, bo jak masz AC to zrobiłeś je prawidłowo.

Albo musisz sobie przygotować funkcje fast I/O w oparciu o getc_unlocked/putc_unlocked albo inne fready(). Na początek możesz też zobaczyć z scanf i printf.

[narbej]

Int, fast i/o and goole are your best friends