Un algoritm naiv, evident, ar fi sa se itereze cu $X$ peste tot intervalul si sa te opresti cand gasesti numarul dorit. Acest algoritm este brute force si are complexitate evidenta O({$P$}), un pic cam incet pentru limitele problemei. Aceasta solutie ia aproximativ 30 de puncte, depinde cum este implementata si se poate vedea "aici":http://infoarena.ro/job_detail/223241?action=view-source
Exista doua solutii eficiente pentru aceasta problema, fiecare cu avantaje si dezavantaje, le voi discuta pe ambele in ceea ce urmeaza:

Pentru prima solutie trebuie sa apelam la teorema lui Ferma care zice ca pentru orice $P$ prim si $N$ , $1 ≤ N ≤ P$, se verifica relatia:

Pentru prima solutie trebuie sa apelam la teorema lui Ferma care zice ca pentru orice $P$ prim si $N$ , $1 ≤ N ≤ P - 1$, se verifica relatia:

$N$^{$P$}^ = {$N$} (%{$P$}).
Pentru intelegerea mai buna a solutiei doresc sa mentionez ca Z{~p~} cu inmultirea formeaza un grup, si asta inseamna ca orice element din Z{~p~} are un invers, unic, deci putem inmulti prin el, chiar daca nu il stim.
In alte cuvinte $N$^{$P$}^ = {$N$} (%{$P$}) | * $N$^-1^