Atenţie! Aceasta este o versiune veche a paginii, scrisă la 2008-12-06 16:17:04.
Revizia anterioară   Revizia următoare  

 

Fişierul intrare/ieşire:inversmodular.in, inversmodular.outSursăArhiva educationala
AutorArhiva EducationalaAdăugată demariusdrgdragus marius mariusdrg
Timp execuţie pe test0.025 secLimită de memorie5120 kbytes
Scorul tăuN/ADificultateN/A

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.ininversmodular.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)} mod N. Putem folosi exponentierea in timp logaritmic pentru a calcula aceasta putere in complexitate O(log2N). 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 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 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. Astfel putem calcula o combinare de ordin N, modulo P, in timp O(N).

Alte aplicatii ce folosesc notiunile prezentate mai sus se regasesc in urmatoarele probleme:

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?