Cod sursa(job #2173948)
Utilizator | Stirbu Vlad Florin vladsf | Data | 16 martie 2018 09:51:42 |
---|---|---|---|
Problema | Invers modular | Scor | 0 |
Compilator | cpp | Status | done |
Runda | Arhiva educationala | Marime | 0.52 kb |
#include <fstream>
using namespace std;
#define ll long long
ifstream f("inversmmodular.in");
ofstream g("inversmmodular.out");
int A, N;
void gcd(ll &x, ll &y, int a, int b)
{
if (!b)
x = 1, y = 0;
else
{
gcd(x, y, b, a % b);
ll aux = x;
x = y;
y = aux - y * (a / b);
}
}
int main()
{
ll inv = 0, ins;
f>>A>>N;
gcd(inv, ins, A, N);
if (inv <= 0)
inv = N + inv % N;
g<<inv;
return 0;
}