Cod sursa(job #2432877)
Utilizator | Teodor Matei Shay | Data | 25 iunie 2019 13:08:02 |
---|---|---|---|
Problema | Invers modular | Scor | 50 |
Compilator | cpp-64 | Status | done |
Runda | Arhiva educationala | Marime | 0.48 kb |
#include <fstream>
#define ll long long
void euclid_extins(int a, int b, ll &x, ll &y) {
if (b == 0) {
x = 1;
y = 0;
} else {
euclid_extins(b, a % b, x, y);
ll temp = x;
x = y;
y = temp - (a / b) * y;
}
}
int main() {
std::ifstream cin("inversmodular.in");
std::ofstream cout("inversmodular.out");
std::ios::sync_with_stdio(false);
int a, n;
ll inv = 0, y;
cin >> a >> n;
euclid_extins(a, n, inv, y);
if (inv <= 0) {
inv += inv % n;
}
cout << inv;
return 0;
}