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 vote219 views1 answer
Print value of data in c++
C++
0 vote224 views1 answer
Error: ‘memset’ was not declared in this scope in cpp
C++
4 votes215 views1 answer
How to make i/o fast in c++
C++
0 vote239 views1 answer
Changing key bindings in visual code not working
C++
0 vote229 views1 answer
MPI_File_seek
C++
14 votes207 views6 answers
How to get size of array c++
C++
-2 votes268 views5 answers
Online c++ graphics compiler
C++
23 votes233 views1 answer
C++ reverse vector
C++
0 vote222 views1 answer
Array di struct
C++
0 vote218 views1 answer
. Single-line comments start with two forward slashes (//).
C++