from random import randrange
from tabelas import *

def divide(x,y):
    if x == 0:
        return y==0
    return y%x==0

def divisores(y):
    """Apenas para y != 0"""
    return {x for x in range(-(abs(y)),abs(y)+1) if divide(x,y)}

def mdc_ingênuo(x,y):
    print(f"Calculando mdc de {x=}, {y=}")
    if y==0:
        return abs(x)
    if x==0:
        return abs(y)
    return max(z for z in divisores(x) if z in divisores(y))

def mdc_ingênuo_v2(x,y):
    res = 1
    for z in range(2,1+min(abs(x), abs(y))):
        if divide(z,x) and divide(z,y):
            res = z
    return res

def Euclides(a, b, printa=False, passo=False):
    Resto_antigo, Resto_novo = a, b
    if printa or passo:
        LRa = [a]
        LRn = [b]
    while Resto_novo != 0:
        Resto_antigo, Resto_novo = Resto_novo, Resto_antigo % Resto_novo
        if printa or passo:
            LRa.append(Resto_antigo)
            LRn.append(Resto_novo)
    if printa or passo:
        printa_tabela(["Resto_antigo", "Resto_novo"],
                      [LRa, LRn],
                      passo)
    else:
        return Resto_antigo
        
mdc = Euclides

def Euclides_estendido(a, b, printa=False, passo=False, restos=False):
    Resto_antigo, Resto_novo = a, b
    x_antigo, y_antigo = 1, 0
    x_novo, y_novo = 0, 1
    if printa or passo:
        print()
        LRa = [a]
        LRn = [b]
        LQ  = []
        Lxa = [x_antigo]
        Lya = [y_antigo]
        Lxn = [x_novo]
        Lyn = [y_novo]
        if restos:
            LR = []
    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 or passo:
            LRa.append(Resto_antigo)
            LRn.append(Resto_novo)
            LQ.append(Quociente)
            Lxa.append(x_antigo)
            Lya.append(y_antigo)
            Lxn.append(x_novo)
            Lyn.append(y_novo)
            if restos:
                LR.append(Resto_novo)
    if printa or passo:
        if not restos:
            printa_tabela(['','Resto_antigo','Resto_novo','Quociente','x_antigo','y_antigo','x_novo','y_novo'],
                        [list(range(len(LRa))),LRa,LRn,LQ,Lxa,Lya,Lxn,Lyn],
                        passo)
        else:
            printa_tabela(['','Resto_antigo','Resto_novo','Quociente', '(resto)','x_antigo','y_antigo','x_novo','y_novo'],
                        [list(range(len(LRa))),LRa,LRn,LQ,LR,Lxa,Lya,Lxn,Lyn],
                        passo)
    else:
        return Resto_antigo, x_antigo, y_antigo