Cod sursa(job #3133674)
Utilizator | Berendea Andrei Berea | Data | 26 mai 2023 16:00:51 |
---|---|---|---|
Problema | Invers modular | Scor | 0 |
Compilator | cpp-64 | Status | done |
Runda | Arhiva educationala | Marime | 0.43 kb |
#include <fstream>
using namespace std;
int a,n,inv,ins;
ifstream cin("input.in");
ofstream cout("input.out");
void solve(int &x, int &y, int a, int b)
{
if (b==0)
{
x=1;
y=0;
}
else
{
solve(x,y,b,a%b);
int aux=x;
x=y;
y=aux-x*(a/b);
}
}
int main()
{
cin>>a>>n;
solve(inv,ins,a,n);
if (inv<=0) inv=n+inv%n;
cout<<inv;
}