Cod sursa(job #2036742)
Utilizator | Dragos Martac Master011 | Data | 11 octombrie 2017 01:27:06 |
---|---|---|---|
Problema | Invers modular | Scor | 100 |
Compilator | cpp | Status | done |
Runda | Arhiva educationala | Marime | 0.56 kb |
#include <stdio.h>
#define ll long long
int A, N;
void gcd(ll &x, ll &y, int a, int b)
{
if (!b)
x = 1, y = 0;
else
{
gcd(x, y, b, a % b);
ll aux = x;
x = y;
y = aux - y * (a / b);
}
}
int main()
{
ll inv = 0, ins;
freopen("inversmodular.in", "r", stdin);
freopen("inversmodular.out", "w", stdout);
scanf("%d %d", &A, &N);
gcd(inv, ins, A, N);
if (inv <= 0)
inv = N + inv;
printf("%lld\n", inv);
return 0;
}