Cod sursa(job #1913772)
Utilizator | Data | 8 martie 2017 13:58:10 | |
---|---|---|---|
Problema | Invers modular | Scor | 100 |
Compilator | cpp | Status | done |
Runda | Arhiva educationala | Marime | 0.51 kb |
#include <fstream>
using namespace std;
ifstream fin("inversmodular.in");
ofstream fout("inversmodular.out");
int EuclidExtins(int a, int b, int &x, int&y);
int main()
{
int A,N;
fin>>A>>N;
int x,y;
EuclidExtins(A,N,x,y);
if(x <= 0)
x = N+ x%N;
fout<<x<<'\n';
return 0;
}
int EuclidExtins(int a, int b, int &x, int&y)
{
if(b == 0)
{ x = 1; y = 0; return a; }
int x1,y1;
int d = EuclidExtins(b,a%b, x1, y1);
x = y1;
y = x1 - y1*(a/b);
return d;
}