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

*Paul*: Problema trebuie pusa pe cazul general cand N si P sunt prime intre ele si refacute testele (si explicatia daca e cazul). E si partial vina mea ca am uitat, dar nu vreau sa restrangem problema.
Se dau doua numere $N$ si $P$, cu $1 ≤ N ≤ P-1$, iar $P$ prim. Sa se determine $X$ intre $1$ si $P-1$ astfel incat $N * X$ sa fie congruent cu {$1$}, modulo $P$ (restul impartirii lui {$N * X$} la $P$ sa fie {$1$}). Numarul $X$ se va numi inversul modular al lui $N$.

Se dau doua numere $N$ si $P$, cu $1 ≤ N ≤ P-1$, iar cmmdc({$N$},{$P$}) = 1. Sa se determine $X$ intre $1$ si $P-1$ astfel incat $N * X$ sa fie congruent cu {$1$}, modulo $P$ (restul impartirii lui {$N * X$} la $P$ sa fie {$1$}). Numarul $X$ se va numi inversul modular al lui $N$.

h2. Date de intrare

* $1 ≤ P ≤ 2.000.000.000$
* $1 ≤ N ≤ P-1$

* Pentru primele $80%$ din teste P este prim.

h2. Exemplu

Un algoritm evident ar fi incercarea tuturor numerelor $X$ intre $1$ si $P-1$ si verificarea proprietatii din enunt pentru $X$. O astfel de solutie are complexitatea {$O(P)$} si obtine 30 de puncte. Sursa se poate gasi 'aici':job_detail/223241?action=view-source.

Complexitatea optima pentru determinarea inversului modular este {$O(log{~2~}P)$}. Din "mica teorema a lui Fermat":http://en.wikipedia.org/wiki/Fermat%27s_little_theorem stim ca $P | X^P-1^-1$, pentru orice numar prim $P$ si pentru orice $X$ prim cu $P$. Demonstratia acestei teoreme se bazeaza pe teoria grupurilor. Din teorema rezulta ca {$X^P-1^ = X * X^P-2^$} este congruent cu $1$, modulo $P$, deci {$X^P-2^$} este inversul modular al lui {$X$}. Solutia problemei va fi deci {$X^P-2^ modulo P$}. Putem folosi 'exponentierea in timp logaritmic':problema/lgput pentru a calcula {$X^P-2^ modulo P$} in complexitate {$O(log{~2~}P)$}. O implementare ce se bazeaza pe aceasta idee se gaseste 'aici':job_detail/226686?action=view-source.

Complexitatea optima pentru determinarea inversului modular este {$O(log{~2~}P)$}. Din "mica teorema a lui Fermat":http://en.wikipedia.org/wiki/Fermat%27s_little_theorem stim ca  {$X^phi(P)^ = 1$}({$%P$}), pentru orice numar $P$ si $X$,pentru care se respecta conditia ca $X$ e relativ prim cu $P$. Demonstratia acestei teoreme se bazeaza pe teoria grupurilor.
Din teorema rezulta ca {$X^phi(P)^ = X * X^phi(P)-1^$} este congruent cu $1$, modulo $P$, deci {$X^phi(P)-1^$} este inversul modular al lui {$X$}. Solutia problemei va fi deci {$X^phi(P)-1^ modulo P$}. Putem folosi 'exponentierea in timp logaritmic':problema/lgput pentru a calcula {$X^phi(P)-1^ modulo P$} in complexitate {$O(log{~2~}P)$}.Pentru cazul particular cand $P$ este prim, $phi(P) = P - 1$, deci raspunsul va fi $X^P-2^$.
O implementare ce se bazeaza pe aceasta idee se gaseste 'aici':job_detail/226686?action=view-source.

O alta abordare optima se bazeaza pe principiul 'extins al lui Euclid':problema/euclid3: oricare ar fi $N$ si $P$ numere intregi exista doua numere intregi $A$ si $B$ astfel incat {$A * N + B * P = cmmdc(N, P)$}. Cum in problema determinarii inversului modular avem $P$ prim, exista $A$ si $B$ astfel incat {$A * N + B * P = 1$}. Considerand ecuatia modulo $P$, deoarece {$B * P$} este divizibil cu {$P$}, avem {$A * N$} congruent cu {$1$} (modulo $P$), deci $A$ este inversul modular pentru {$N$}. Complexitatea acestui algoritm este tot {$O(log{~2~}P)$}, deoarece coeficientii $A$ si $B$ pot fi determinati in timp logaritmic. {$A$} poate sa fie si negativ, deci trebuie sa adaugam $P$ la $A$ pana devine pozitiv. O astfel de solutie se poate gasi 'aici':job_detail/226687?action=view-source.

O alta abordare optima se bazeaza pe principiul 'extins al lui Euclid':problema/euclid3: oricare ar fi $N$ si $P$ numere intregi exista doua numere intregi $A$ si $B$ astfel incat {$A * N + B * P = cmmdc(N, P)$}. Cum in problema determinarii inversului modular avem $P$ prim, exista $A$ si $B$ astfel incat {$A * N + B * P = 1$}. Considerand ecuatia modulo $P$, deoarece {$B * P$} este divizibil cu {$P$}, avem {$A * N$} congruent cu {$1$} (modulo $P$), deci $A$ este inversul modular pentru {$N$}. Complexitatea acestui algoritm este tot {$O(log{~2~}P)$}, deoarece coeficientii $A$ si $B$ pot fi determinati in timp logaritmic. {$A$} poate sa fie si negativ, deci trebuie sa adaugam $P$ la $A$ pana devine pozitiv.
 
O astfel de solutie se poate gasi 'aici':job_detail/226687?action=view-source.

Ambele rezolvari pot fi extinse la cazul cand $P$ nu este prim si {$cmmdc(N, P) = 1$}.