3次方程式の実数根の個数 (ふか杯 3rd Contest 03E)

http://rose.u-aizu.ac.jp/onlinejudge/ProblemSet/description.jsp?id=2220&lang=jp

問題

略

解法

解法は主に3通りある。
1つ目は二部探索により実数解をひとつ見つけ、その解を使って次数を一つ落として二次方程式の解の公式を使って解く方法。
2つ目はカルダノの公式を使う方法(本当に解けるかどうかは知らない)。
3つ目はn次多項式を一階微分して、n-1次多項式に直したあと、その解を求め、-∞,n-1次多項式の解,∞の(最大)n個の区間に分割して二部探索で解を求める方法。
私は1,3の方法でやったが、コンテスト本番ではBairstow's methodと言う方法を使って解かれました。