#! /usr/bin/env python
# -*- coding: UTF-8 -*-

""" PyRuffini di Frafra (francesco.it@gmail.com)

    This program is free software; you can redistribute it and/or modify
    it under the terms of the GNU General Public License as published by
    the Free Software Foundation; either version 2 of the License, or
    (at your option) any later version.

    This program is distributed in the hope that it will be useful,
    but WITHOUT ANY WARRANTY; without even the implied warranty of
    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
    GNU General Public License for more details.
"""  

# Intestazione
__module_name__ = "PyRuffini"
__module_version__ = "1.0-rc1"
__module_description__ = "Scompone i polinomi con la regola di Ruffini"

# Importa le librerie
from sys import exit

def ask(message, valid_chars):
    """ Funzione per l'inserimento dei dati """
    for each in xrange(10):
        answer = raw_input(message + " ")
        if answer not in valid_chars:
            print "Formato non valido, riprova."
        else:
            if len(answer) == 1 or (len(answer) == 2 and answer[0] == "-"):
                return answer
            else:
                print "Formato non valido, riprova."
    print "L'utente è troppo stupido per usare questo programma."
    exit(1)

# Inizializza le variabili
p = []
div = []
div2 = []
display = []
delete = []

# Grado del polinomio
g = int(ask("Grado:", [str(x+2) for x in xrange(8)]))

# Chiede il polinomio
for x in xrange(g+1):
    p.append(int(ask("Coefficente di X^"+str(g-x)+":", [str(x-9) for x in xrange(19)])))

# Modulo del termine noto
tnp = abs(p[-1])

# Calcola i divisori
for x in xrange(tnp):
    if tnp%(x+1)==0:
        div.append(tnp/(x+1))
        div.append(-tnp/(x+1))

# Trova il divisore che fa diventare A(x) = 0
for x in xrange(len(div)):
    somma = p[0]
    for y in xrange(len(p)-1):
        somma = somma*div[x]+p[y+1]
    if somma == 0:
        div2.append(div[x])

# Verifica che ci siano divisori
if len(div2) == 0:
    print "Non esistono divisori."
    exit(1)

# Scompone
res = [p[0]]
for x in xrange(len(p)-1):
    res.append(res[-1]*div2[0]+p[x+1])

# Normalizza il risultato
for x in xrange(len(res)-2):
    display.append(str(res[x])+"x^"+str(len(res)-x-2))
display.append(str(res[-2]))

for x in xrange(len(display)):
    if display[x][0] != "-":
        display[x] = "+"+display[x]
    if display[x][-2:] == "^1":
        display[x] = display[x][:-2]
    elif display[x][-2:] == "^0":
        display[x] = display[x][:-3]
    if display[x] != display[-1]:
        if display[x][1] == "1":
            display[x] = display[x][0]+display[x][2:]
        if display[x][1] == "0":
            delete.append(display[x])
for x in xrange(len(delete)):
    del display[display.index(delete[x])]

if display[0][0] == "+":
    display[0] = display[0][1:]

if str(div2[0])[0] == "-":
    n = "+"+str(div2[0])[1:]
else:
    n = "-"+str(div2[0])[0:]

# Visualizza il risultato
print "("+"".join(display)+")(x"+n+")"