h2. Restricţii
* $1 &le; A < N &le; 2.000.000.000$

* Pentru $70%$ din teste $N$ este prim.

* Pentru $60%$ din teste $N$ este prim.

h2. Exemplu

O complexitate mai buna se obtine folosind "teorema lui Euler":http://en.wikipedia.org/wiki/Euler%27s_theorem, din care avem ca <tex>A^{\varphi(N)} \equiv 1 (mod N)</tex>, unde <tex>\varphi(N)</tex> reprezinta numarul numerelor mai mici decat $N$ si prime cu $N$. Cum <tex>A^{\varphi(N)} = A * A^{\varphi(N)-1}</tex> rezulta ca <tex>A^{\varphi(N)-1}</tex> este inversul modular al lui {$A$}. Solutia problemei va fi deci <tex>A^{\varphi(N)-1} mod N</tex>. Putem folosi 'exponentierea in timp logaritmic':problema/lgput pentru a calcula aceasta putere in complexitate {$O(log{~2~}N)$}. In plus, putem calcula <tex>\varphi(N)</tex> in complexitate <tex>O(\sqrt{N})</tex>. Pentru cazul particular cand $N$ este prim, <tex>\varphi(N) = N-1</tex>, deci raspunsul va fi $A^N-2^$ (dupa cum reiese si din "mica teorema a lui Fermat":http://en.wikipedia.org/wiki/Fermat%27s_little_theorem). O implementare ce se bazeaza pe aceasta idee se gaseste 'aici':job_detail/227473?action=view-source.

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

Complexitatea optima pentru determinarea inversului modular este {$O(log{~2~}N)$}. Putem folosi principiul 'extins al lui Euclid':problema/euclid3: oricare ar fi $A$ si $N$ numere intregi exista doua numere $X$ si $Y$ de asemenea intregi astfel incat {$A * X + N * Y = cmmdc(A, N)$}. Cum in problema determinarii inversului modular avem {$cmmdc(A, N) = 1$}, exista $X$ si $Y$ astfel incat {$A * X + N * Y = 1$}. Considerand ecuatia modulo $N$, deoarece {$N * Y$} este divizibil cu {$N$}, avem {$A * X$} congruent cu {$1$} (modulo $N$), deci $X$ este inversul modular pentru {$A$}. Coeficientii $X$ si $Y$ pot fi determinati in timp logaritmic. {$X$} poate sa fie si negativ, deci trebuie sa adaugam $N$ la $X$ pana cand devine pozitiv. O astfel de solutie se poate gasi 'aici':job_detail/228208?action=view-source.

h2. Aplicatii

Alte aplicatii ce folosesc notiunile prezentate mai sus se regasesc in urmatoarele probleme:

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

* 'Functii':problema/functii

* 'Jap2':problema/jap2
* "The equation":http://acm.sgu.ru/problem.php?contest=0&problem=106, sgu
* "Stand in Line":http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=23&page=show_problem&problem=2115, uva

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

3451