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 N si P ,cu 1 ≤ N ≤ P - 1, iar P este 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

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 http://infoarena.ro/job_detail/223241?action=view-source
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, se verifica relatia:
N^P = N (% P ).
Pentru intelegerea mai buna a solutiei doresc sa mentionez ca Z~p~ cu inmultirea formeaza un grup, si asta inseamna ca orice element din Z~p~ are un invers, unic, deci putem inmulti prin el, chiar daca nu il stim.
In alte cuvinte N^P = N (%$P$) | * N^-1
N^{P - 1} = 1 (% P ), deci :
N * N^{P - 2} = 1 (% P );
De unde se observa ca N^{P - 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(log ₂ P). O astfel de implementare se poate vedea aici http://infoarena.ro/job_detail/223243?action=view-source .
A 2-a solutie, se bazeaza pe un simplu principiu. Anume cel al euclidului extins, si anume 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( http://infoarena.ro/problema/euclid3). Se presupune ca le putem gasi in complexitate O( M ). cmmdc( N , P ) = 1, deoarece N ≤ P - 1 iar P este prim. Deci avem ca A * N + B * P = 1, ecuatie care o transformam in Z~p~,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(log~2~ M ).

Cum se trimit solutii?