Revizia anterioară Revizia următoare
| 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
| inversmodular.in | inversmodular.out |
|---|---|
| 5 7 | 3 |
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(log2P). 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:
Nphi(P) = 1 (%P).
In alte cuvinte
NP-1 = 1 (%P), deci :
N * NP-2 = 1 (%P);
De unde se observa ca NP-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(log2P). 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(log2M). 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 Zp ,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(log2 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.
