Cod sursa(job #2871224)
Utilizator | Data | 13 martie 2022 18:17:02 | |
---|---|---|---|
Problema | Invers modular | Scor | 90 |
Compilator | cpp-64 | Status | done |
Runda | Arhiva educationala | Marime | 0.44 kb |
#include <fstream>
void euclid_extins(int a, int b, int &x, int &y) {
if (b == 0) {
x = 1;
y = 0;
return;
}
int xx = x, yy = y;
euclid_extins(b, a % b, xx, yy);
x = yy;
y = xx - yy * (a / b);
}
int main() {
std::ifstream fin("inversmodular.in");
std::ofstream fout("inversmodular.out");
int a, n;
fin >> a >> n;
int x, y;
euclid_extins(a, n, x, y);
fout << (x + n) % n;
return 0;
}