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

Se dau doua numere $N$ si $P$, cu $1 ≤ N ≤ P-1$, iar $N$ si $P$ sunt prime intre ele({$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$.

Se dau doua numere $N$ si $P$, cu $1 ≤ N ≤ P-1$, $N$ si $P$ sunt prime intre ele ({$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

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 cmmdc({$N$},{$P$})=1, 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.

h4. Probleme similare
 
* "p11174":http://icpcres.ecs.baylor.edu/onlinejudge/index.php?option=com_onlinejudge&Itemid=8&category=23&page=show_problem&problem=2115

h2. Aplicatii
* "Stand in Line":http://icpcres.ecs.baylor.edu/onlinejudge/index.php?option=com_onlinejudge&Itemid=8&category=23&page=show_problem&problem=2115 (uva)

* "functii":problema/functii

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