Cod sursa(job #1611576)
Utilizator | Data | 24 februarie 2016 11:39:03 | |
---|---|---|---|
Problema | Invers modular | Scor | 100 |
Compilator | cpp | Status | done |
Runda | Arhiva educationala | Marime | 0.53 kb |
#include<cstdio>
using namespace std;
int a,n;
int keepx,keepy,oldx,oldy;
void solve(int v1,int v2)
{
if(v2==0)
{
oldx=v1;
oldy=0;
return;
}
solve(v2,v1%v2);
keepx=oldy;
keepy=oldx-(v1/v2)*oldy;
oldx=keepx;
oldy=keepy;
}
int main()
{
freopen("inversmodular.in","r",stdin);
freopen("inversmodular.out","w",stdout);
scanf("%d %d",&a,&n);
solve(a,n);
while(keepx<=0)
{
keepx+=n;
}
printf("%d",keepx);
}