Cod sursa(job #3232891)
| Utilizator | Data | 1 iunie 2024 20:16:23 | |
|---|---|---|---|
| Problema | Invers modular | Scor | 100 |
| Compilator | cpp-64 | Status | done |
| Runda | Arhiva educationala | Marime | 0.65 kb |
#include <iostream>
#include <fstream>
#define ll long long
using namespace std;
int X, M;
void extendedGCD(ll &u, ll &v, int p, int q)
{
if (!q)
u = 1, v = 0;
else
{
extendedGCD(u, v, q, p % q);
ll temp = u;
u = v;
v = temp - v * (p / q);
}
}
int main()
{
long long inverse = 0, tempVar;
ifstream fin("inversmodular.in");
ofstream fout("inversmodular.out");
fin >> X >> M;
extendedGCD(inverse, tempVar, X, M);
if (inverse <= 0)
inverse = M + inverse % M;
fout << inverse << endl;
return 0;
}