Lược đồ Horner

Để chia đa thức $f(x) = a_nx^n + a_{n-1}x^{n-1} + \dots + a_1x + a_0$ cho nhị thức $g(x) = x - c$ người ta thường sử dụng lược đồ Horner theo dạng bảng:

Trong đó:
$b_n = a_n$, $b_{n-1} = c.b_n + a_{n-1}$, $b_{n-2} = c.b_{n-1} + a_{n-2}$, …, $b_1 = c.b_2 + a_1$, $b_0 = c.b_1 + a_0$

Hay ta viết:
$b_n = a_n$, $\quad b_i = c.b_{i+1} + a_i \; (i = 0..n-1)$

Khi đó ta có biến đổi đa thức:
$f(x) = (x - c)(b_nx^{n-1} + b_{n-1}x^{n-2} + \dots + b_1) + b_0$

Từ đó ta có kết luận: $x = c$ là nghiệm của đa thức $f(x)$ nếu $b_0 = 0$.

Hãy lập chương trình nhập vào các hệ số $a_i$ của đa thức $f(x)$ và giá trị $c$, tính các hệ số $b_i$ và cho biết $c$ có là nghiệm của đa thức $f(x)$ hay không.

Dữ liệu vào trong file Horner.INP có cấu trúc như sau:

• Dòng đầu chứa số tự nhiên $n$ và số nguyên $c$ ($n < 100$, $|c| < 5000$).
• $n+1$ dòng tiếp theo mỗi dòng chứa một số nguyên lần lượt là các hệ số $a_i$ của đa thức $f(x)$ với ($|a_i| < 5000$) được sắp xếp từ $a_n$ đến $a_0$.

Dữ liệu ra là file Horner.OUT có cấu trúc như sau:

• Dòng đầu tiên là kết luận: "c la nghiem" hoặc "c khong la nghiem".
• $n+1$ dòng tiếp theo, liệt kê các hệ số $b_i$ sắp xếp từ $b_n$ đến $b_0$.

• $n < 100$, $|c| < 5000$, $|a_i| < 5000$.