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($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.

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$).

{$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^
$N$^{$P - 1$}^ = {$1$} (%$P$), deci :
$N$ * $N$^{$P - 2$}^ = {$1$} (%$P$);
De unde se observa ca $N$^{$P - 2$}^ este defapt $X$ -ul cautat. Deci solutia, pe scurt pentru cei care nu sunt prea interesati de demonstratie este sa ridicam $N$ la puterea $P - 2$ modulo $P$, si acest numar va fi rezultatul dorit. Ridicarea la putere se face in timp logaritmic, deci complexitate finala este O(log ~2~ $P$).
 

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

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