Cod sursa(job #595854)
Utilizator | Gramatovici Paul gramatovici_paul | Data | 14 iunie 2011 17:34:10 |
---|---|---|---|
Problema | Invers modular | Scor | 100 |
Compilator | cpp | Status | done |
Runda | Arhiva educationala | Marime | 0.39 kb |
#include<stdio.h>
void euclid (int a,int b,int &x,int &y)
{
if (b==0)
{
x=1;
y=0;
return;
}
int xx,yy;
euclid(b,a%b,xx,yy);
x=yy;
y=xx-yy*(a/b);
}
int main()
{
int a,n,x,y;
freopen("inversmodular.in","r",stdin);
freopen("inversmodular.out","w",stdout);
scanf("%d%d",&a,&n);
euclid(a,n,x,y);
if (x>0)
printf("%d",x%n);
else
printf("%d",n+x%n);
}