Cod sursa(job #2738330)
Utilizator | Data | 5 aprilie 2021 18:23:35 | |
---|---|---|---|
Problema | Invers modular | Scor | 100 |
Compilator | cpp-64 | Status | done |
Runda | Arhiva educationala | Marime | 0.48 kb |
#include <iostream>
#include <fstream>
#define ll long long
using namespace std;
ifstream fin("inversmodular.in");
ofstream fout("inversmodular.out");
ll a, MOD, x, y;
ll euclidExtins(ll a, ll b)
{ if(!b)
{ x = 1;
y = 0;
return a;
}
ll g = euclidExtins(b, a % b);
ll x1 = y, y1 = x - y * (a / b);
x = x1;
y = y1;
return g;
}
int main()
{
fin >> a >> MOD;
ll g = euclidExtins(a, MOD);
while(x < 0)
x += MOD;
fout << x << '\n';
return 0;
}