5853. Majątek Billa

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.

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

Zaimplementowałem “modularne potęgowanie przez podnoszenie do kwadratu”:
https://pastebin.com/g8GcQ5Zd59 (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.

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.

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

Autor określił, iż zadanie można napisać w językach programowania: All except: ASM64 GOSU.
Uczę się programowania w języku Python. Najpierw napisałem program z użyciem potęgowania i modulo. Niestety otrzymałem rezultat, iż przekroczono limit czasu. Następnie z użyciem wbudowanej funkcji pow() i znów przekroczyłem limit czasu. Na koniec skorzystałem z napisanej przez kogoś funkcji realizującej szybkie potęgowanie modularne i tak jak się spodziewałem znów przekroczenie liczby czasu.

Przeglądając „wszystkie zgłoszenia” i „najlepsze” zauważyłem, iż zadanie rozwiązali jedynie posługujący się językami z rodziny C. Skoro tylko kompilator C potrafi w tym czasie przetworzyć dane, to czy języki programowania nie powinny być ograniczone jedynie do tych z rodziny C? Po co marnować czas na zadanie którego nie można w innym języku rozwiązać w określonym czasie?

Nic takiego autor nie określił. Po prostu nie zabronił abyś zgłaszał rozwiązanie w którymś z licznej plejady dostępnych języków programowania. Autor już i tak poświęcił wystarczaj ąco dużo czasu na przygotowanie zadania i nie jest w stanie sprawdzić czy rozwiązanie przejdzie w którym kolwiek innym języku niż w użytym przez autora.

Jeżeli tak uważasz, to rzeczywiście po co?

Słabo przeglądałeś:

Mnie też boli wyśrubowanie czasów w niektórych zadaniach. Często wymusza to stosowanie fast-io co niekoniecznie jest wygodne i proste. Może udałoby się polepszyć trochę taką sytuację przemnażając maksymalny czas wykonania zadania w danym języku programowania?

P.S. @narbej Czy mógłbyś mi powiedzieć jak taki zwykły szary hipopotam SPOJa może uzyskać dostęp do pełnych statystyk (obecnie widzę tylko 11 stron z najlepszymi wynikami)? Kiedyś o ile dobrze pamiętam można było zobaczyć najlepsze czasy w danym języku. Teraz tego nie widzę ;/

Też tak mam
Ale można dopisać lang=…
Gdzie, zamiast kropek wstawiasz kod języka. Dla mniej popularnych języków raczej zmieścisz się w 11 stronach. Kody poznasz, klikając w dany język, np na stronie: https://pl.spoj.com/problems/latwe/7

Mnie też kiedyś, ale pocieszę Cię, poboli poboli i przestanie.