Cod sursa(job #2784305)
Utilizator | Data | 16 octombrie 2021 11:51:48 | |
---|---|---|---|
Problema | Invers modular | Scor | 100 |
Compilator | cpp-64 | Status | done |
Runda | Arhiva educationala | Marime | 0.44 kb |
#include <iostream>
#include <fstream>
#define ll long long
using namespace std;
ifstream fin ("inversmodular.in");
ofstream fout("inversmodular.out");
pair<ll, ll>invers(ll x, ll y)
{
if(y == 0) return {1, 0};
auto p = invers(y, x%y);
return {p.second, p.first - p.second*(x/y)};
}
int main()
{
int a, n;
fin >> a >> n;
ll b = invers(a, n).first;
while(b < 0) b+=n;
fout << b;
return 0;
}