def get_all_divisors_brute(n):
    n = n if n > 0 else -n
    for i in range(1, int(n / 2) + 1):
        if n % i == 0:
            yield i
    yield n


def get_poly_value(i, cf, x):
    if i == 0:
        return cf[i]
    else:
        value = get_poly_value(i - 1, cf, x)
        return cf[i] + x * value


def divide(n, cfs):
    new_cfs = [cfs[0]]
    current = cfs[0]

    for i in cfs[1::]:
        current = current * n + i
        new_cfs.append(current)

    if new_cfs[-1] == 0:
        return True, new_cfs[:-1]
    else:
        return False, cfs


def horner_schema(poly_cf, dividers={}):
    divisors = get_all_divisors_brute(poly_cf[-1])
    for i in divisors:
        res, cfs = divide(i, poly_cf)

        if res:
            poly_cf = cfs
            if i not in dividers.keys():
                dividers[i] = 1
            else:
                dividers[i] += 1
            return horner_schema(poly_cf, dividers)
        else:
            another_res, another_new_cfs = divide(-i, poly_cf)
            if another_res:
                poly_cf = another_new_cfs
                if -i not in dividers.keys():
                    dividers[-i] = 1
                else:
                    dividers[-i] += 1
                return horner_schema(poly_cf, dividers)

    return poly_cf, dividers


def get_roots_from_dict(roots):
    roots = list(roots.keys())
    if roots == []:
        print("Многочлен неприводим")
    else:
        print("Список корней многочлена:", roots)


if __name__ == "__main__":
    print('Введите коэффициенты многочлена: ')
    cf = list(map(int, input().split()))
    n = len(cf) - 1

    print("================================")
    print("== Вычисление корней полинома ==")
    print("================================")
    _, root_dict = horner_schema(cf)
    get_roots_from_dict(root_dict)

    print()
    print("==================================")
    print("== Вычисление значения полинома ==")
    print("==================================")
    x = int(input("Введите x: "))
    y = get_poly_value(n, cf, x)
    print(f"Значение полинома в точке {x} = {y}")