If you solve this problem with a help of finding roots of the initial polynom, use long long or __int64 type in this function! This fact costed me about 5 submissions...
This is the part of my code:

long long PolynomValue (vector<int>PolynomCoeffs, int x0)
{
long long value;
...
return value;
}

int FindRoot (vector<int> PolynomCoeffs)
{
...
if (!PolynomValue(PolynomCoeffs,a)) return a;
...
}
If I changed long long to int I would not find a root in several cases.

To understand me more clearly try these tests:

-20000 19998 20000 -19999
(x-1)(x-1)(x+1)(x-19999)

-19998 -20000 20000 -19999
(x-19999)(x3+x2-x+1)

-19999 -19999 -19999 -20000
(x+1)(x-20000)(x2+1)

I guess 13th and 14th tests are something like these ones.
Good luck!

Edited by author 22.01.2010 21:07