#include "stdafx.h"

int Euclid3(int a,int b,int *x,int *y)
{
	int d;
	int c[1000];
	int i=-1;
	int r;

	while(b!=0){
		r=a%b;
		c[++i]=a/b;
		a=b;
		b=r;
	}
	d=a;

	if(i>0){
		--i;
		*x = 1;
		*y = -c[i];
		--i;
		int aux;
	
		while(i>=0)
		{
			aux = *x;
			*x = *y;
			*y = aux -c[i]*(*y);
			--i;
		}
	}
	else if(i==0){
		*x=0;
		*y=1;
	}
	else if(i==-1){
		*x=1;
		*y=0;
	}
	return d;
}

int _tmain(int argc,char* argv[])
{
	int A=5,N=7;
	int x,y;
	FILE *fpr,*fpw;
	fpr = fopen("inversmodular.in","r");
	fpw = fopen("inversmodular.out","w");

	fscanf(fpr,"%d %d",&A,&N);
	Euclid3(A,N,&x,&y);
	if(x>N)
		x=x%N;
	else if(x<0)
		x=(x%N)+N;
	fprintf(fpw,"%d",x);

	fclose(fpr);
	fclose(fpw);
	return 0;
}