Extended euclidean algorithm

Extended euclidean python

def extendEuclidean(a, b, s1=1, s2=0, t1=0, t2=1):
    
    if b:
        r=a%b
        return extendEuclidean(b, r, s2, s1-s2*(a//b), t2, t1-t2*(a//b))
    
    return a, s1, t1

Extended euclidean algorithm

int gcd(int a, int b, int& x, int& y) {
    if (b == 0) {
        x = 1;
        y = 0;
        return a;
    }
    int x1, y1;
    int d = gcd(b, a % b, x1, y1);
    x = y1;
    y = x1 - y1 * (a / b);
    return d;
}

Source: cp-algorithms.com

Similar codes

0 vote99 views2 answers
Change colour of output to terminal c++
C++
0 vote101 views1 answer
C++ handling
C++
0 vote90 views2 answers
Interface in c++
C++
5 votes99 views2 answers
How to convert a string to a double c++
C++
0 vote101 views2 answers
C++ programming code to remove all characters from string except alphabets
C++
28 votes103 views5 answers
Flutter date format
C++
2 votes95 views1 answer
Cannot find -lsqlite3 C++ compiler error
C++
16 votes96 views6 answers
Sort vector c++
C++
23 votes100 views1 answer
C++ reverse vector
C++
3 votes108 views2 answers
Cpp map insert
C++