Cod sursa(job #823015)
Utilizator | Soucup Nicolae Silviu DxH5dIMHN | Data | 24 noiembrie 2012 14:13:58 |
---|---|---|---|
Problema | Invers modular | Scor | 100 |
Compilator | cpp | Status | done |
Runda | Arhiva educationala | Marime | 0.52 kb |
#include <iostream>
#include <fstream>
using namespace std;
void euclid_extins(long long a, long long b, long long *d, long long *x, long long *y)
{
if (b == 0)
{
*d = a;
*x = 1;
*y = 0;
}
else
{
long long x0, y0;
euclid_extins(b, a % b, d, &x0, &y0);
*x = y0;
*y = x0 - (a / b) * y0;
}
}
int main ()
{
long long A,N,d,x,y;
ifstream fi("inversmodular.in");
ofstream fo("inversmodular.out");
fi>>A>>N;
euclid_extins(A,N,&d,&x,&y);
while(x<0) x += N;
fo << x << "\n";
return 0;
}