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

Se dau doua numere $N$ si $P$ ,cu $1 ≤ N ≤ P-1$, iar $P$ prim. Sa se determine $X$ ( $1 ≤ X ≤ M-1$) astfel incat ({$N$}*{$X$}) = 1(%{$P$})

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

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 $N$ si $P$, 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 ≤ N ≤ P-1$

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({$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 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 "teorema lui Fermat":http://en.wikipedia.org/wiki/Fermat%27s_little_theorem
 

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 - 1$, se verifica relatia:

$N$^phi({$P$})^ = {$1$} (%{$P$}).
In alte cuvinte

$N$^{$P$}^ = {$N$} (%{$P$}).
Pentru intelegerea mai buna a solutiei doresc sa mentionez ca Z{~p~}(multimea tuturor resturilor posibile la impartirea cu $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$). O astfel de implementare se poate vedea "aici":http://infoarena.ro/job_detail/223243?action=view-source .
A 2-a solutie, se bazeaza pe un simplu principiu, anume cel al euclidului extins, care zice ca exista doua numere $A$ si $B$, intregi, astfel incat $A$ * $N$ + $B$ * $P$ = cmmdc({$N$},{$P$}). Nu voi intra in detalii in legatura cu algoritmul de gasire a acestor numere $A$ si $B$, algoritm care se gaseste in Cormen sau chiar pe "infoarena":http://infoarena.ro/problema/euclid3. Se presupune ca le putem gasi in complexitate O(log{~2~}{$M$}). cmmdc({$N$},{$P$}) = 1, deoarece $N$ ≤ $P-1$ iar $P$ este prim. Deci avem ca $A$ * $N$ + $B$ * $P$ = $1$, ecuatie care o transformam in $Z{~p~}$ ,in alte cuvinte modulo $P$, si rezulta $A$ * $N$ + $0$ = $1$, fiindca $B$ * $P$ e divizibil cu $P$,din motive evidente. $A$ * $N$ = $1$ (% $P$ ), Se observa din nou ca $A$ este $X$ -ul cautat. Din pacate acum $A$ -ul poate sa fie si negativ, deci trebuie sa adaugam $P$ la $A$ pana devine pozitiv. Complexitatea O(log{~2~} $P$).

 
 
h4. Avantaje si Dezavantaje
Ne vom referi la primul algoritm optim(cel cu ridicarea la putere) ca prima rezolvare si la celalalt algoritm ca a 2a rezolvare ,pentru dezambiguizare.
Prima rezolvare are urmatoarele avantaje: e usor de demonstrat si implicit de tinut minte, e usor de implementat si nu foloseste functii recursive si nici nu face operatii care sa incetineasca programul. Dezavantajul consta in faptul ca solutia nu e flexibila si nu poate fi extinsa pentru cazul cand cmmdc({$P$},{$N$}) = $1$.
A 2-a rezolvare e mai greu de implementat, poate da overflow si in practica se comporta mai prost decat prima, desi complexitatea e aceeasi. Dar aceasta problema poate fi adaptata pentru cazul cand $P$ nu este prim si se stie doar ca $N$ si $P$ sunt relativ prime, in alte cuvinte au cmmdc({$P$},{$N$}) = $1$.

h4. Folosinta:

Cel mai des Inversul modular se foloseste in dinamici,mai ales cand avem combinari sau aranjamente si trebuie sa calculam modulo un numar prim. De exemplu in loc sa calculam $combinari(N,P)= N!/(((N-P)!*P!)$ calculam $combinari(N,P) = N! * INVERS($(N-P)$) * INVERS($P$)$.

Cel mai des Inversul modular se foloseste in dinamici,mai ales cand avem combinari sau aranjamente si trebuie sa calculam modulo un numar prim. De exemplu in loc sa calculam $combinari(N,P)= N!/(((N-P)!*P!)$ calculam $combinari(N,P) = N! * INV($(N-P)$!) * INV($P$!)$.

h4. Probleme similare