Cod sursa(job #2479476)
Utilizator | Axinte Teodor TeodorAxinte | Data | 23 octombrie 2019 21:05:44 |
---|---|---|---|
Problema | Invers modular | Scor | 100 |
Compilator | cpp-64 | Status | done |
Runda | Arhiva educationala | Marime | 0.46 kb |
#include <bits/stdc++.h>
#define INT long long int
using namespace std;
ifstream fin("inversmodular.in");
ofstream fout("inversmodular.out");
INT n,a,x,y,d;
void cmmdc(INT,INT,INT&,INT&);
int main()
{
fin>>a>>n;
INT x,y;
cmmdc(a,n,x,y);
x=x%n;
if(x<0)x+=n;
fout<<x;
return 0;
}
void cmmdc(INT a,INT b,INT &x,INT &y)
{
if(b==0){x=1;y=0;return;}
INT x0,y0;
cmmdc(b,a%b,x0,y0);
x=y0;
y=x0-a/b*y0;
}