Cod sursa(job #311323)
Utilizator | Sanduleac Dan sandyxp | Data | 3 mai 2009 11:42:18 |
---|---|---|---|
Problema | Invers modular | Scor | 100 |
Compilator | cpp | Status | done |
Runda | Arhiva educationala | Marime | 0.45 kb |
#include <fstream>
using namespace std;
#define NUME "inversmodular"
ifstream fi(NUME".in");
ofstream fo(NUME".out");
void gcd(long long &x, long long &y, int a, int b) {
if (!b)
x = 1, y = 0;
else
{
gcd(x, y, b, a % b);
long long t = y;
y = x - (a/b) * y;
x = t;
}
}
int main()
{
long long x, y;
int A, N;
fi >> A >> N;
gcd(x, y, A, N);
fo << (x+N) % N << endl;
return 0;
}