The problem is given an integral coefficient polynomial, find all integral roots of it.
If there is repeated root, output them repeatedly.
For the integral roots of the polynomial, it must be a factor of the constant term of the polynomial. We then can factorized the constant term and verify the factors to the polynomial one by one.
However, overflow will occur during the verification (the degree of the polynomial may be as large as 100), how should we verify the solution safely?
One method is that you can calculate the polynomial by repeatedly dividing and subtracting each terms. For example, ax^2 + bx + c = 0, it can be rewritten as ax + b = -c/x. As the LHS of the equation is integer, the c/x must be integer. Using this method, we can avoid overflow in our calculation.
This has not solved the problem. We have not identified the repeated roots. One way to find the multiplicity of roots is to check f(x), f'(x), f''(x), and so on, and they should all be zero. But calculating the derivatives of f may again lead to overflow.
The method I finally used is to do polynomial division.
I repeatedly divide the polynomial by (x - c). If that is divisible, then c is a root of it, and use the quotient to continue the process. This can avoid all overflow problems, and find the repeated roots successfully.
Be careful on the cases that zero is the root of the polynomial.
沒有留言:
張貼留言