﻿ Tips And Tutorial - Presented by Oneous!

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
**************************/``````