class Polynome:
    def __init__(self,*coefs):
        if type(coefs[0]) == tuple:
            self.coefs = [ i for i in coefs[0] ]
        else:   
            self.coefs = coefs        
        self.deg = len( self.coefs ) - 1
        
    # addition
    
    def __add__(self, Q):
        n = max(self.deg, Q.deg)
        V = [ 0 ] * ( n - min(self.deg, Q.deg) )
        if self.deg > Q.deg:
            A = V  + list(Q.coefs)
            B = list(self.coefs)
        else:
            A = V + list(self.coefs)
            B = list(Q.coefs)
        
        return Polynome( tuple( [ A[i]+B[i] for i in range(n+1) ] ) )
    
    # soustraction
    
    def __sub__(self, Q):
        n = max(self.deg, Q.deg)
        V = [ 0 ] * ( n - min(self.deg, Q.deg) )
        if self.deg > Q.deg:
            B = V  + list(Q.coefs)
            A = list(self.coefs)
        else:
            A = V + list(self.coefs)
            B = list(Q.coefs)
        
        return Polynome( tuple( [ A[i]-B[i] for i in range(n+1) ] ) )
    
    # multiplication
    
    def __mul__(self, Q):
        dico_P = { self.deg-i:self.coefs[i] for i in range(len(self.coefs)) }
        dico_Q = { Q.deg-i:Q.coefs[i] for i in range(len(Q.coefs)) }
        dico_R = {}
        for degP, coefP in dico_P.items():
            for degQ, coefQ in dico_Q.items():
                if degP+degQ not in dico_R:
                    dico_R[ degP+degQ ] = coefP * coefQ
                else:
                    dico_R[ degP+degQ ] += coefP * coefQ
        R = [ v for k,v in dico_R.items() ]
        
        return Polynome( tuple(R) )
    
    # affichage
    
    def __str__(self):
        E = { u[0]:"x" + chr(u[1]) for u in ((2,0x00B2), (3,0x00B3), (4,0x2074), (5,0x2075), (6,0x2076), (7,0x2077), (8,0x2078), (9,0x2079)) }
        E[0] = '' 
        E[1] = 'x'
        if self.deg > 9:
            for d in range( self.deg - 9 ):
                E[ 10+d ] = 'x^{'+str(10+d)+'}'
        start = True
        D = { self.deg-i:self.coefs[i] for i in range( len( self.coefs ) ) }
        R = ''
        for k,v in D.items():
            if v > 0:
                if not start:
                    R += '+'
                else:
                    start = False
                if v == 1:
                    if k != 0:
                        R += E[k]
                    else:
                        R += '1'
                else:
                    R += str(v) + E[k]
            elif v < 0:
                if v == -1:
                    if k != 0:
                        R += '-' + E[k]
                    else:
                        R += '-1'
                else:   
                    R += str(v) + E[k]
        return str(R)
    
    # Hörner
    
    def horner(self,r):
        Q = [ self.coefs[0] ]
        for k in range( 1 , len(self.coefs)-1 ):
            Q.append( self.coefs[k] + r*Q[k-1] )
        
        return Polynome( tuple(Q) )
    
    # Recherche de racines avec le théorème de Viète
    # "P admet une racine rationnelle p/q si p divise a(0) et q divise a(n) si tous les coefs sont entiers"
    
    def rationnal_roots(self):
        from fractions import Fraction
        L = [ i for i in range(1,abs(self.coefs[0])+1) if self.coefs[0]%i == 0 ] # liste des diviseurs de a(n)
        M = [ i for i in range(1,abs(self.coefs[-1])+1) if self.coefs[-1]%i == 0 ] # liste des diviseurs de a(0)
        F = [] # liste des fractions potentiellement racines
        for p in M:
            for q in L:
                if Fraction(p,q) not in F:
                    F.append( Fraction(p,q) )
                    F.append( Fraction(-p,q) )
                    
        R = []            
        for f in F:
            sum_terms = 0
            for i in range( len(self.coefs) ):
                sum_terms += self.coefs[i] * ( f**(self.deg-i) )
                
            if sum_terms == 0:
                R.append( f.__str__() )
                
        return R
    
P = Polynome(1,-1,1,-1)
Q = Polynome(1,-1,-2)

print( Q.rationnal_roots() )

print(P)
print(Q)