10104

//Extended euclid Algorithm
#include <iostream>

using namespace std;

long long int gcd(long long int a, long long int b)
{
     if(b==0)
     return a;
     else
     return gcd(b,a%b);
}

int main()
{
    long long int a,b,g,q,temp,t1,t2;


    while(cin>>a>>b)
    {
       //g=gcd(a,b);
       long long int prevx=1,x=0,y=1,prevy=0;

       while(b)
       {
         q=a/b;
         t1=x;
         x=prevx-q*x;
         prevx=t1;
         t2=y;
         y=prevy-q*y;
         prevy=t2;
         temp=a;
         a=b;
         b=temp%b;
       }
       cout<<prevx<<" "<<prevy<<" "<<a<<"\n";
    }
    return 0;
}

Theory:

The pseudo code of the extended euclid algorithm:

xgcd(a,b):
prevx, x = 1, 0; prevy, y = 0, 1
while (b!=0)
{

q = a/b
x = prevx – q*x;

prevx= x;
y = prevy – q*y;

prevy= y;
a = b;

b= a % b;

}
return a, prevx, prevy

[button color=”red” size=”small” link=”https://www.dropbox.com/s/f44huwxpczagql5/extended%20euclid%20algorithm.pdf?dl=0″ target=”blank” ]Download[/button]