Pagini recente » Cod sursa (job #785172) | Cod sursa (job #633214) | Cod sursa (job #512136) | Cod sursa (job #676727) | Cod sursa (job #1947318)
#include <cstdio>
using namespace std;
int a, n;
inline void euclid(int a, int b, long long &x, long long &y){
if(b == 0){
x = 1; y = 0;
return ;
}
long long x0, y0;
euclid(b, a % b, x0, y0);
x = y0;
y = x0 - y0 * (a / b);
}
int main()
{
freopen("inversmodular.in", "r", stdin);
freopen("inversmodular.out", "w", stdout);
scanf("%d%d", &a, &n);
long long ins, inv = 0;
euclid(a, n, inv, ins);
if(inv <= 0) inv = n + inv % n;
printf("%lld\n", inv);
return 0;
}