Cod sursa(job #1146321)
Utilizator | Data | 18 martie 2014 21:10:20 | |
---|---|---|---|
Problema | Invers modular | Scor | 50 |
Compilator | cpp | Status | done |
Runda | Arhiva educationala | Marime | 0.55 kb |
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
void euclid(int a, int b, int &d, int &x, int &y)
{
if(b == 0)
{
d = a;
x = 1;
y = 0;
return;
}
int x0, y0;
euclid(b, a%b, d, x0, y0);
x = y0;
y = x0 - y0*(a/b);
}
int main()
{
freopen("inversmodular.in", "r", stdin);
freopen("inversmodular.out", "w", stdout);
int n, a;
scanf("%d%d", &a, &n);
int d, x, y;
euclid(n, a, d, x, y);
printf("%d\n", y);
return 0;
}