Cod sursa(job #1957014)
Utilizator | Dumbravean Bogdan dumbraveanb | Data | 7 aprilie 2017 11:29:57 |
---|---|---|---|
Problema | Invers modular | Scor | 100 |
Compilator | cpp | Status | done |
Runda | Arhiva educationala | Marime | 0.52 kb |
#include <iostream>
#include <fstream>
using namespace std;
ifstream fin("inversmodular.in");
ofstream fout("inversmodular.out");
#define ll long long
int a, n;
ll inv, ins;
void Inv(ll& x, ll&y, int a, int b) {
if(!b)
x = 1, y = 0;
else {
Inv(x, y, b, a % b);
ll aux = x;
x = y;
y = aux - y * (a / b);
}
}
int main()
{
fin >> a >> n;
Inv(inv, ins, a, n);
if(inv <= 0)
inv = n + inv % n;
fout << inv;
return 0;
}