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 teorema lui Fermat
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:
NP = N (%P).
Pentru intelegerea mai buna a solutiei doresc sa mentionez ca Zp(multimea tuturor resturilor posibile la impartirea cu P) cu inmultirea formeaza un grup, si asta inseamna ca orice element din Zp are un invers, unic, deci putem inmulti prin el, chiar daca nu il stim.
In alte cuvinte NP = N (%P) | * N-1
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. 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.
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! * INV$!) * INV$.
