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

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 ≤ A < N ≤ 2.000.000.000
Pentru 60% 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 $A^{\varphi(N)} \equiv 1 (mod N)$ , unde $\varphi(N)$ reprezinta numarul numerelor mai mici decat N si prime cu N. Cum $A^{\varphi(N)} = A * A^{\varphi(N)-1}$ rezulta ca $A^{\varphi(N)-1}$ este inversul modular al lui A. Solutia problemei va fi deci $A^{\varphi(N)-1} mod N$ . Putem folosi exponentierea in timp logaritmic pentru a calcula aceasta putere in complexitate O(log₂N). In plus, putem calcula $\varphi(N)$ in complexitate $O(\sqrt{N})$ . Pentru cazul particular cand N este prim, $\varphi(N) = N-1$ , deci raspunsul va fi A^N-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(log₂N). 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 N, deoarece N * Y este divizibil cu N, avem A * X congruent cu 1 (modulo N), deci X este inversul modular pentru A. Coeficientii X si Y pot fi determinati in timp logaritmic. X poate sa fie si negativ, deci trebuie sa adaugam N la X pana cand devine pozitiv. O astfel de solutie se poate gasi aici.

Aplicatii

O aplicatie foarte utila a inversilor modulari este calcularea combinarilor, modulo un numar prim P dat. De exemplu, avem:

$C^K_N = \frac{N!}{K!*(N-K)!} = N! * (K!)^{-1} * [(N-K)!]^{-1}$

Prin $(K!)^{-1}$ si $[(N-K)!]^{-1}$ se inteleg inversii modulari ai acestor numere, modulo P. Astfel putem calcula o combinare de ordin N, modulo P, in timp O(N).