Cod sursa(job #1398312)
Utilizator | Data | 24 martie 2015 09:25:00 | |
---|---|---|---|
Problema | Invers modular | Scor | 100 |
Compilator | cpp | Status | done |
Runda | Arhiva educationala | Marime | 0.57 kb |
#include<cstdio>
int gcd(int a,int b,long long int &x,long long int &y)
{
if(!b)
{
x=1;
y=0;
}
else
{
long long int temp;
gcd(b,a%b,x,y);
temp=x;
x=y;
y=temp-(a/b)*y;
}
}
int main()
{
FILE *fin,*fout;
fin=fopen("inversmodular.in","r");
fout=fopen("inversmodular.out","w");
int a,n;
fscanf(fin,"%d %d",&a,&n);
long long int inv=0,ins;
gcd(a,n,inv,ins);
if(inv<=0)
{
inv=n+inv%n;
}
fprintf(fout,"%lld",inv);
}