def extended_gcd(a, b):
    """
    extended_gcd(a : int, b : int) ->
    (gcd : int, x : int, y : int)

    Use Euclid's extended algorithm to find the greatest common divisor as well
    as x and y so that ax + by = gcd(a, b).
    """
    if b > a:
        a, b = b, a
    x = 0, 1
    y = 1, 0
    while b != 0:
        quotient = a // b
        a, b = b, a % b
        x = x[1] - quotient * x[0], x[0]
        y = y[1] - quotient * y[0], y[0]
    return a, x[1], y[1]
