Notebook/src-bkp/Extended GCD.cpp
pair<int, pair<int, int> > extendedEuclid(int a, int b) {
    int x = 1, y = 0;
    int xLast = 0, yLast = 1;
    int q, r, m, n;
    while(a != 0) {
        q = b / a;
        r = b % a;
        m = xLast - q * x;
        n = yLast - q * y;
        xLast = x, yLast = y;
        x = m, y = n;
        b = a, a = r;
    }
    return make_pair(b, make_pair(xLast, yLast));
}
/* This function return the gcd of a and b followed by
    the pair x and y of equation ax + by = gcd(a,b)*/
This function return the gcd of a and b followed by
the pair x and y of equation ax + by = gcd(a,b)
This function return the gcd of a and b followed by the pair x and y of equation ax + by = gcd ( a b )
pair<int, pair<int, int> > extendedEuclid(int a, int b) {
    int x = 1, y = 0;
    int xLast = 0, yLast = 1;
    int q, r, m, n;
    while(a != 0) {
        q = b / a;
        r = b % a;
        m = xLast - q * x;
        n = yLast - q * y;
        xLast = x, yLast = y;
        x = m, y = n;
        b = a, a = r;
    }
    return make_pair(b, make_pair(xLast, yLast));
}
pair < int , pair < int , int > > extendedEuclid ( int a , int b ) { int x = 1 , y = 0 ; int xLast = 0 , yLast = 1 ; int q , r , m , n ; while ( a != 0 ) { q = b / a ; r = b % a ; m = xLast - q * x ; n = yLast - q * y ; xLast = x , yLast = y ; x = m , y = n ; b = a , a = r ; } return make_pair ( b , make_pair ( xLast , yLast ) ) ; }
This function return the gcd of a and b followed by
the pair x and y of equation ax + by = gcd(a,b)
This function return the gcd of a and b followed by the pair x and y of equation ax + by = gcd ( a b )