Tóm tắt đề bài: Cho phương trình ~ax^3 + bx^2 + cx + d = 0~, với ~a, b, c, d~ là các số nguyên dương và ~\le 1000~. Tìm một nghiệm bất kỳ của phương trình này.

Có thể chứng minh phương trình này luôn có nghiệm âm. Một nghiệm dương sẽ dẫn tới vô lý, vì cả phương trình sẽ lớn hơn ~0~.

Gọi ~f (x) = ax^3 + bx^2 + cx + d~.

Xét đạo hàm ~f' (x) = 3ax^2 + 2bx + c~. Xét ~\triangle = (2b)^2 - 4 \times 3a \times c = 4b^2 - 12ac~.

Nếu ~\triangle \le 0~, thì ~f(x)~ sẽ đồng biến trên ~R~. Vì vậy, ta có thể tìm kiếm nhị phân để tìm ra nghiệm.

Ngược lại, ~f'(x)~ sẽ có hai nghiệm ~x_1, x_2~ với ~x_1 < x_2~. Theo tính chất tam thức bậc hai, ta có ~f'(x) < 0~ với mọi ~x_1 < x < x_2~, hay ~f(x)~ nghịch biến trên ~(x_1, x_2)~. Ngược lại, ~f(x)~ sẽ đồng biến trên ~(-\infty, x_1]~ và ~[x_2, \infty)~. Từ đó, ta có thể chia ba trường hợp và tìm kiếm nhị phân.

Vì sai số cho phép bài này rất nhỏ (~10^{-9}~), nên ta sẽ cần chia đôi miền nghiệm khoảng ~10^6~ lần.

Độ phức tạp: ~O~ (~10^6~).