== include(page="template/taskheader" task_id="inversmodular") ==

Se dau doua numere $N$ si $P$ (cu $1 ≤ N ≤ P - 1$). $P$ este prim. Sa se determine $X$ ( $1 ≤ X ≤ M - 1$) astfel incat ({$N$}*{$X$}) = 1(%{$P$})

Se dau doua numere $N$ si $P$ ,cu $1 ≤ N ≤ P - 1$, iar  $P$ este prim. Sa se determine $X$ ( $1 ≤ X ≤ M - 1$) astfel incat ({$N$}*{$X$}) = 1(%{$P$})

h2. Date de intrare

h2. Indicaţii de rezolvare

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(M), 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:
{$N$^$P$^} = {$N$} (%$P$), in alte cuvinte

== include(page="template/taskfooter" task_id="inversmodular") ==