Extended Euclidean Algorithm
Last Update: 6 March, 2009

Problem:

The extended Euclidean algorithm is an extension to the Euclidean algorithm for finding the greatest common divisor (GCD) of integers a and b: it also finds the integers x and y in

ax + by = gcd(a,b);

(Typically either x or y is negative).
The extended Euclidean algorithm is particularly useful when a and b are co-prime, since x is the modular multiplicative inverse of a modulo b.

 

My Code:

#include<cstdio>
#include<cmath>
#include<iostream>
using namespace std;
#define MAX(a,b)  ((a>b)?a:b)
#define MIN(a,b)  ((a<b)?a:b)

typedef struct {
	int d,x,y;
}result;

result extendedEuclid(int a, int b) {
	result res,resp;
	if(b==0) {		
		res.d=a;
		res.x=1;
		res.y=0;
		return res;
	}
	resp=extendedEuclid(b,a%b);
	res.d=resp.d;
	res.x=resp.y;
	res.y=resp.x-((a/b)*resp.y);
	return res;
}

int main()
{
	//freopen("in.txt","rt",stdin)
	//freopen("out.txt","wt",stdout)

	int a,b,x,y,d;

	while(scanf("%d %d",&a,&b)==2) {
		if(a==0&&b==0)
			break;
		result res=extendedEuclid(a,b);
		printf("X = %d, Y = %d, D = %d\n",res.x,res.y,res.d);

	}
return 0;
}




/******  Programmed by:
	~  ORONNO  ~
	www.the1.co.nr
**************************/