Atenţie! Aceasta este o versiune veche a paginii, scrisă la 2008-12-01 10:49:31.
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 N si P ,cu 1 ≤ N ≤ P-1, iar P prim. Sa se determine X ( 1 ≤ X ≤ M-1) astfel incat (N*X) = 1(%P)

Date de intrare

Se citesc numerele N si P, separate printr-un spatiu.

Date de ieşire

Se va tipari numarul X cerut in enunt.

Restricţii

  • 1 ≤ P ≤ 2.000.000.000
  • 1 ≤ N ≤ P

Exemplu

inversmodular.ininversmodular.out
5 7
3

Explicaţie

5 * 3 = 15 = 14 + 1 = 7 * 2 + 1
deci (5 * 3) % 7 = 1

Indicaţii de rezolvare

Un algoritm naiv, evident, ar fi sa se itereze cu X peste tot intervalul si sa te opresti cand gasesti numarul dorit. Acest algoritm este brute force si are complexitate evidenta O(P), un pic cam incet pentru limitele problemei. Aceasta solutie ia aproximativ 30 de puncte, depinde cum este implementata si se poate vedea aici
Exista doua solutii eficiente pentru aceasta problema, fiecare cu avantaje si dezavantaje, le voi discuta pe ambele in ceea ce urmeaza:
Pentru prima solutie trebuie sa apelam la teorema lui Ferma care zice ca pentru orice P prim si N , 1 ≤ N ≤ P - 1, se verifica relatia:
N{phi($P$)} = 1 (%P).
In alte cuvinte
NP-1 = 1 (%P), deci :
N * NP-2 = 1 (%P);
De unde se observa ca NP-2 este defapt X -ul cautat. Deci solutia, pe scurt pentru cei care nu sunt prea interesati de demonstratie este sa ridicam N la puterea P-2, modulo P, si acest numar va fi rezultatul dorit. Ridicarea la putere se face in timp logaritmic, deci complexitate finala este O(log2P). O astfel de implementare se poate vedea aici .
A 2-a solutie, se bazeaza pe un simplu principiu, anume cel al euclidului extins, care zice ca exista doua numere A si B, intregi, astfel incat A * N + B * P = cmmdc(N,P). Nu voi intra in detalii in legatura cu algoritmul de gasire a acestor numere A si B, algoritm care se gaseste in Cormen sau chiar pe infoarena. Se presupune ca le putem gasi in complexitate O(log2M). cmmdc(N,P) = 1, deoarece NP-1 iar P este prim. Deci avem ca A * N + B * P = 1, ecuatie care o transformam in Zp ,in alte cuvinte modulo P, si rezulta A * N + 0 = 1, fiindca B * P e divizibil cu P,din motive evidente. A * N = 1 (% P ), Se observa din nou ca A este X -ul cautat. Din pacate acum A -ul poate sa fie si negativ, deci trebuie sa adaugam P la A pana devine pozitiv. Complexitatea O(log2 P).

Folosinta:

Cel mai des Inversul modular se foloseste in dinamici,mai ales cand avem combinari sau aranjamente si trebuie sa calculam modulo un numar prim. De exemplu in loc sa calculam combinari(N,P)= N!/(((N-P)!*P!) calculam combinari(N,P) = N! * INV$!) * INV$.

Probleme similare

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?