Extended Euclid source code

Tutorial Link : http://blog.forthright48.com/2015/07/extended-euclidean-algorithm.html

Theorem : Let the solutions be X and Y , this algorithm gives the result as |X| + |Y | is the minimal. If there are several X and Y satisfying the minimal criteria, then the result follows the condition X ≤ Y.

Source Code :

#include<bits/stdc++.h>

using namespace std;


int X=-1,Y=-1;

int ext_gcd ( int A, int B){
    int x2, y2, x1, y1, x, y, r2, r1, q, r;
    x2 = 1; y2 = 0;
    x1 = 0; y1 = 1;
    for (r2 = A, r1 = B; r1 != 0; r2 = r1, r1 = r, x2 = x1, y2 = y1, x1 = x, y1 = y ) {
        q = r2 / r1;
        r = r2 % r1;
        x = x2 - (q * x1);
        y = y2 - (q * y1);
    }
    X = x2;
    Y = y2;

    return r2;
}

int main()
{
    int a,b;
    cin>>a>>b;

    int e=ext_gcd(a,b);

    cout<<"Gcd is :"<<e<<" and x="<<X<<" y="<<Y;
}