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 A si N, cu 1 ≤ A ≤ N-1, prime intre ele (cel mai mare divizor comun al lor este 1). Sa se determine X intre 1 si N-1 astfel incat A * X sa fie congruent cu 1, modulo N (restul impartirii lui A * X la N sa fie 1). Numarul X se va numi inversul modular al lui A.
Date de intrare
Fisierul de intrare inversmodular.in va contine pe prima linie numerele A si N, 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 ≤ N ≤ 2.000.000.000
- 1 ≤ A ≤ N-1
- Pentru 70% din teste N este prim.
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 N-1 si verificarea proprietatii din enunt pentru X. O astfel de solutie are complexitatea O(N) si obtine 30 de puncte. Sursa se poate gasi aici.
O complexitate mai buna se obtine folosind teorema lui Euler, din care avem ca Aphi(N) este congruent cu 1, modulo N, unde phi(N) reprezinta numarul numerelor mai mici decat N si prime cu N. Cum Aphi(N) = A * Aphi(N)-1 rezulta ca Aphi(N)-1 este inversul modular al lui A. Solutia problemei va fi deci Aphi(N)-1 modulo N. Putem folosi exponentierea in timp logaritmic pentru a calcula Aphi(N)-1 modulo N in complexitate O(log2N). Putem sa calculam phi(N) in complexitate 
. Pentru cazul particular cand N este prim, phi(N) = N-1, deci raspunsul va fi AN-2 (dupa cum reiese si din mica teorema a lui Fermat). O implementare ce se bazeaza pe aceasta idee se gaseste aici.
Complexitatea optima pentru determinarea inversului modular este O(log2P). Putem folosi principiul extins al lui Euclid: oricare ar fi A si N numere intregi exista doua numere X si Y de asemenea intregi astfel incat A * X + N * Y = cmmdc(A, N). Cum in problema determinarii inversului modular avem cmmdc(A, N) = 1, exista X si Y astfel incat A * X + N * Y = 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.
Aplicatii
- Stand in Line (uva)
- functii
