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 - 1$, se verifica relatia:

$N$^{phi($P$)}^ = {$1$} (%{$P$}).

$N$^phi({$P$})^ = {$1$} (%{$P$}).

In alte cuvinte
$N$^{$P-1$}^ = {$1$} (%{$P$}), deci :
$N$ * $N$^{$P-2$}^ = {$1$} (%{$P$});