inversmodular

Invers modular

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

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

Se dau doua numere $A$ si $N$, cu $1 ≤ A ≤ N-1$, prime intre ele (cel mai mare divizor comun al lor este $1$). Sa se determine $X$ intre $1$ si $N-1$ astfel incat $A * X$ sa fie congruent cu {$1$}, modulo $N$ (restul impartirii lui {$A * X$} la $N$ sa fie {$1$}). Numarul $X$ se va numi inversul modular al lui $A$.

h2. Date de intrare

Se citesc numerele $N$ si $P$, separate printr-un spatiu.

Fisierul de intrare $inversmodular.in$ va contine pe prima linie numerele $A$ si $N$, separate printr-un spatiu.

h2. Date de ieşire

Se va tipari numarul $X$ cerut in enunt.

Fisierul de iesire $inversmodular.out$ va contine pe prima linie numarul $X$ cu proprietatea din enunt.

h2. Restricţii

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

* $1 &le; A < N &le; 2.000.000.000$
* Pentru $60%$ din teste $N$ este prim.

h2. Exemplu

h3. Explicaţie

$5 * 3 = 15 = 14 + 1 = 7 * 2 + 1$
deci $(5 * 3) % 7 = 1$

$5 * 3$ este congruent cu {$1$}, modulo {$7$}, deoarece restul impartirii lui $15$ la $7$ este {$1$}.

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

Un algoritm evident ar fi incercarea tuturor numerelor $X$ intre $1$ si $N-1$ si verificarea proprietatii din enunt pentru $X$. O astfel de solutie are complexitatea {$O(N)$} si obtine 30 de puncte. Sursa se poate gasi 'aici':job_detail/223241?action=view-source.
 
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~}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
 
O aplicatie foarte utila a inversilor modulari este calcularea combinarilor, modulo un numar prim $P$ dat. De exemplu, avem:
 
<tex>C^K_N = \frac{N!}{K!*(N-K)!} = N! * (K!)^{-1} * [(N-K)!]^{-1}</tex>
 
Prin <tex>(K!)^{-1}</tex> si <tex>[(N-K)!]^{-1}</tex> se inteleg inversii modulari ai acestor numere, modulo {$P$}. Astfel putem calcula o combinare de ordin $N$, modulo $P$, in timp {$O(N)$}.
 
Alte aplicatii ce folosesc notiunile prezentate mai sus se regasesc in urmatoarele probleme:
 
* '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