Pagini recente » Cod sursa (job #400925) | Cod sursa (job #2180611) | Cod sursa (job #2413904) | Cod sursa (job #706649) | Cod sursa (job #2509911)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("inversmodular.in");
ofstream fout("inversmodular.out");
#define ll long long
int A, N;
void Euclid(ll &x, ll &y, int a, int b)
{
if(b == 0) {
x = 1;
y = 0;
}
else {
Euclid(x, y, b, a % b);
ll aux = x;
x = y;
y = aux - y * (a / b);
}
}
int main()
{
fin.tie(NULL);
fin >> A >> N;
ll inv = 0, ins;
Euclid(inv, ins, A, N);
if(inv <= 0)
inv = N + inv % N;
fout << inv << "\n";
}