17206. Gra w mnożenie [AL_12_03]

Zadanie:
http://spoj.com/ALGOLIGA/problems/AL_12_03
http://pl.spoj.com/problems/AL_12_03

Skrócony opis problemu:

Zaczynamy od $p=1$. Gracze A i B mnożą na przemian $p$ przez $x \in \left\lbrace 2,3,4,5,6,7,8,9\right\rbrace$ aż $p \ge n$. Gracz, który ostatni przemnoży $p$ wygrywa. Zaczyna gracz A. Naszym zadaniem jest określić który gracz wygra, zakładając, że obaj grają optymalnie.

17204. Winda [AL_12_01]

Zadanie:
http://spoj.com/ALGOLIGA/problems/AL_12_01
http://pl.spoj.com/problems/AL_12_01

Skrócony opis zadania:

Jest nam dany string (o długości $m$) opisujący historię operacji windy. Litera D oznacza, że winda pojechała jedno piętro w dół, a U oznacza, że pojechała do góry. Naszym zadaniem jest stwierdzić czy dana historia jest poprawna, czyli winda nie zjechała poniżej parteru (o numerze 1) lub nie wjechała powyżej najwyższego piętra (o numerze $n$).

12219. Jasio kryptolog [AL_01_04]

Zadanie:
https://pl.spoj.com/problems/AL_01_04

Skrócony opis problemu:

Zadanie dotyczy szyfrowania RSA, więc na pewno przed jego rozwiązywaniem należy zapoznać się z tym systemem na przykład pod tym linkiem: RSA na wikipedii.

Na wejściu dostajemy dwie różne liczby pierwsze $p,q<4\cdot 10^9$ oraz liczbę $e<\phi(pq), \ \gcd(e,\phi(pq))=1$, tak że para $(pq,e)$ stanowi klucz publiczny szyfrowania. Oznaczmy $n=pq$. Chcemy się dowiedzieć ile komunikatów ze zbioru $\left\{0,..,n-1\right\}$ po zaszyfrowaniu taką metodą nie zmienia swojej postaci. Inaczej mówiąc pytamy o: $\left|\left\{M\in\left\{0,..,n-1\right\}: M^e \equiv M \pmod{n}\right\}\right|$ - liczbę punktów stałych szyfrowania RSA.