Question

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(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(log2N). 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).

Answer 1

Ai rezolvarea in fisierul atasat...

afbe4f311f027a8481ab984ce3995d3b.cpp