Cod sursa(job #624041)
Utilizator | Data | 21 octombrie 2011 16:04:03 | |
---|---|---|---|
Problema | Invers modular | Scor | 100 |
Compilator | cpp | Status | done |
Runda | Arhiva educationala | Marime | 0.45 kb |
#include<stdio.h>
void f1(int a,int b, int &x, int &y)
{
if (b==0)
{
x=1;
y=0;
return ;
}
int x1,y1,q=a/b;
f1(b,a%b,x1,y1);
x=y1;
y=x1-y1*q;
}
int main ()
{
int a,n,x,y;
freopen("inversmodular.in","r",stdin);
freopen("inversmodular.out","w",stdout);
scanf("%d %d",&a,&n);
f1(a,n,x,y);
x%=n;
if (x<0)
x=x+n;
printf("%d",x);
return 0;
}