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
Paul: Problema trebuie pusa pe cazul general cand N si P sunt prime intre ele si refacute testele (si explicatia daca e cazul). E si partial vina mea ca am uitat, dar nu vreau sa restrangem problema.
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). Numarul X se va numi inversul modular al lui N.
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 P | XP-1-1, pentru orice numar prim P si pentru orice X prim cu P. Demonstratia acestei teoreme se bazeaza pe teoria grupurilor. Din teorema rezulta ca XP-1 = X * XP-2 este congruent cu 1, modulo P, deci XP-2 este inversul modular al lui X. Solutia problemei va fi deci XP-2 modulo P. Putem folosi exponentierea in timp logaritmic pentru a calcula XP-2 modulo P in complexitate O(log2P). O implementare ce se bazeaza pe aceasta idee se gaseste aici.
O alta abordare optima se bazeaza pe principiul extins al lui Euclid: oricare ar fi N si P numere intregi exista doua numere intregi A si B astfel incat A * N + B * P = cmmdc(N, P). Cum in problema determinarii inversului modular avem P prim, exista A si B astfel incat A * N + B * P = 1. Considerand ecuatia modulo P, deoarece B * P este divizibil cu P, avem A * N congruent cu 1 (modulo P), deci A este inversul modular pentru N. Complexitatea acestui algoritm este tot O(log2P), deoarece coeficientii A si B pot fi determinati in timp logaritmic. A poate sa fie si negativ, deci trebuie sa adaugam P la A pana devine pozitiv. O astfel de solutie se poate gasi aici.
Ambele rezolvari pot fi extinse la cazul cand P nu este prim si cmmdc(N, P) = 1.
Probleme similare
Cel mai des determinarea inversului modular este utila in calcularea combinarilor modulo un numar prim P dat. Pentru a calcula Comb(K, N) = N! / .. latex here.., calculam...
