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 ( 1 ≤ X ≤ M-1) astfel incat (N*X) = 1(%P)
Date de intrare
Se citesc numerele N si P, separate printr-un spatiu.
Date de ieşire
Se va tipari numarul X cerut in enunt.
Restricţii
- 1 ≤ P ≤ 2.000.000.000
- 1 ≤ N ≤ P
Exemplu
| inversmodular.in | inversmodular.out |
|---|---|
| 5 7 | 3 |
Explicaţie
5 * 3 = 15 = 14 + 1 = 7 * 2 + 1
deci (5 * 3) % 7 = 1
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
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).
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$) * INVERS$.
