15488. Wyspa do zasiedlenia [AL_11_09]

[quenthui]

pl.spoj.com/problems/AL_11_09/
Witam
Od jakiegoś czasu walczę z tym zadaniem. Utknąłem na max testach, na których dostaje TL. Gdzie tu jeszcze można ukraść cenne sekundy? Wszystko liczę tylko raz, z wzorów. Żadnych podwójnych pętli itp. Czy limity czasowe nie są trochę zbyt mocno wyśrubowane jak na te dane wejściowe?

mój kod:
[bbone=CPP,1755]
// tu był kod
[/bbone]

EDIT: Jeszcze nie zrobiłem, ale wiadomo o co chodzi, więc usuwam kod

EDIT2: W końcu się udało

[quenthui]

W żadnym wypadku nie kwestionuję poziomu trudności.
A co do pola wyspy. Może mieści się ono w long longu. Ale podczas jego liczenia łatwo przeskoczyć zakres.

[quenthui]

Racja, racja. Próbowałem tak zrobić. Ale z powodu innych błędów nie działo.
I w sumie źle sformułowałem pytanie. Nie tyle jak wykorzystać małe twierdzenie Fermata, ale jak z niego wywnioskować, że można w taki sposób sumować kolonistów?

[witman]

Zgodnie z MTF, jeżeli p jest liczbą pierwszą, to dla dowolnej liczby całkowitej [tex]a[/tex], mamy [tex]a^p - a \equiv 0\ (mod\ p)[/tex].
Idąc dalej, dla [tex]0Czyli:
[tex]a^{p-1} \equiv a^0[/tex]
[tex]a^p \equiv a^1[/tex]
[tex]a^{p+1} \equiv a^2[/tex]
itd....
czyli wartości potęg powtarzają się co p-1.

Twoje zgłoszenie nr 12256274 jest prawie idealne. Musisz tylko uwzględnić pewien szczególny przypadek, o którym pisałem w uwadze na końcu opisu zadania na forum Algoligi.

Jeśli miałbyś ochotę rozwiązać więcej moich zadań, to polecam np. takie dwa (IMHO jedne z ciekawszych), których przygotowanie zajęło mi wiele czasu: Znaki dymne i Jak Bajtek mechanizmy wielce złożone konstruował