Fişierul intrare/ieşire:	inversmodular.in, inversmodular.out	Sursă	Arhiva educationala
Autor	Arhiva Educationala	Adăugată de	dragus marius •mariusdrg
Timp execuţie pe test	0.025 sec	Limită de memorie	5120 kbytes
Scorul tău	N/A	Dificultate	N/A

Poti vedea testele pentru aceasta problema accesand atasamentele.

Vezi solutiile trimise | Statistici

Invers modular

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

Date de intrare

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

Date de ieşire

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

Restricţii

• 1 ≤ P ≤ 2.000.000.000
• 1 ≤ N ≤ P-1

Exemplu

Explicaţie

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

Indicaţii de rezolvare

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.

Complexitatea optima pentru determinarea inversului modular este O(log₂P). Din mica teorema a lui Fermat stim ca

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-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₂P). O astfel de implementare se poate vedea aici .
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. Se presupune ca le putem gasi in complexitate O(log₂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₂ P).

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.
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.
Ambele rezolvari pot fi extinse la cazul cand P nu este prim si cmmdc(N,P) = 1.

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! * (N-P)!^-1 * P!^-1.

Probleme similare

• p11174

Cum se trimit solutii?