Revizia anterioară Revizia următoare
| 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
| inversmodular.in | inversmodular.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(M), 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:
{NP} = N (%$P$), in alte cuvinte
