def extended_euclidian(a, b):
    """
    returns (x, y, d) such that:
    x*a + y*b = d, d = gcd(a,b)

    r_1 = a - b * q_1
    r_2 = b - r_1 * q_2
    ...
    r_n = r_n-2 - r_n-1*q_n = a * x_n + b * y_n

    x_n = x_n-2 - x_n-1 * q_n
    y_n = y_n-2 - y_n-1 * q_n
    """

    # Naive version:
    # x2, y2 = 1, 0
    # x1, y1 = 0, 1
    # while b > 0:
    #     q, a, b = a // b, b, a % b
    #     x = x2 - x1 * q
    #     y = y2 - y1 * q
    #     x2, x1 = x1, x
    #     y2, y1 = y1, y
    # return x2, y2, a

    # Recursive version O(log^2(a))
    # suppose we know x1, y1 for (b, a%b) and a%b = a - b*q
    # then b*x1 + (a%b)*y1 = a*y1 + b*(x1 - y1*q)
    if a == b == 0:
        return 0, 0, 0
    if b == 0:
        return 1, 0, a
    x, y, d = extended_euclidian(b, a % b)
    return y, x - y * (a // b), d