Cod sursa(job #2374234)
Utilizator | Ababei Daniel Googal | Data | 7 martie 2019 17:36:22 |
---|---|---|---|
Problema | Invers modular | Scor | 100 |
Compilator | cpp-64 | Status | done |
Runda | Arhiva educationala | Marime | 0.5 kb |
#include <iostream>
#include <fstream>
using namespace std;
ifstream in("inversmodular.in");
ofstream out("inversmodular.out");
typedef long long ll;
int a, n;
ll inv, ins;
void inv_mod(ll &inv, ll &ins, int a, int b) {
if(b == 0) {
inv = 1;
ins = 0;
} else {
inv_mod(inv, ins, b, a % b);
swap(inv, ins);
ins -= inv * (a / b);
}
}
int main()
{
in >> a >> n;
inv_mod(inv, ins, a, n);
inv = (inv + n) % n;
out << inv << '\n';
in.close();
out.close();
return 0;
}