def mdc(a,b,printa=False):
    dividendo, divisor = abs(a), abs(b)
    resto = dividendo % divisor
    if printa:
        print(f'{dividendo=}, {divisor=}, {resto=}')
    while resto > 0:
        dividendo, divisor = divisor, resto
        resto = dividendo % divisor
        if printa:
            print(f'{dividendo=}, {divisor=}, {resto=}')
    return divisor

def mdc_DRY(a,b, printa=False):
    dividendo, divisor = abs(a), abs(b)
    i = 0
    l_dividendo = len(str(dividendo))
    l_divisor = len(str(divisor))
    while True:
        i += 1
        resto = dividendo % divisor
        
        if printa:
            print(f'{i:>3}. {dividendo = :<{l_dividendo}} | {divisor = :<{l_divisor}} | {resto = }')
        if resto == 0:
            return divisor
        dividendo, divisor = divisor, resto

def mdc_estendido(a, b, printa=False):
    resto_antigo, resto_novo = abs(a), abs(b)
    x_antigo, x_novo = 1, 0
    y_antigo, y_novo = 0, 1
    if printa:
        print(f'{resto_antigo = }, {x_antigo = }, {y_antigo = }, {resto_novo = }')
    while resto_novo > 0:
        resto_antigo, (quociente, resto_novo) = resto_novo, divmod(resto_antigo, resto_novo)
        x_antigo, x_novo = x_novo, (x_antigo - quociente*x_novo)
        y_antigo, y_novo = y_novo, (y_antigo - quociente*y_novo)
        if printa:
            print(f'{resto_antigo = }, {x_antigo = }, {y_antigo = }, {resto_novo = }')
    return resto_antigo, x_antigo, y_antigo

def mdc_estendido_DRY(a, b, printa=False):
    if printa:
        print(f'{a = }, {b = }')
        print()
    dividendo, divisor       = abs(a), abs(b)
    x_dividendo, y_dividendo = (a > 0) - (a < 0), 0
    x_divisor, y_divisor     = 0, (b > 0) - (b < 0)

    while True:
        quociente, resto = divmod(dividendo, divisor)

        if printa:
            print(f'{dividendo = }, {divisor = }, {quociente = }, {resto = }, fim = {resto==0}')
            print(f' ↳ {x_divisor = }, {y_divisor = }, {x_divisor*a = }, {y_divisor*b = }')
            print()

        if resto == 0:
            if printa:
                print('Fim!')
            return divisor, x_divisor, y_divisor

        dividendo, divisor     = divisor, resto
        x_dividendo, x_divisor = x_divisor, (x_dividendo - quociente*x_divisor)
        y_dividendo, y_divisor = y_divisor, (y_dividendo - quociente*y_divisor)

def mdc_(a, b):
    dividendo, divisor = abs(a), abs(b)

    while True:
        resto = dividendo % divisor

        if resto == 0:
            return divisor

        dividendo, divisor = divisor, resto