题解：P1024 [NOIP2001 提高组] 一元三次方程求解

· · 题解

首先，最简便的方法是使用盛金公式。

假设方程为 ax^3+bx^2+cx+d=0，那么：

令 \begin{cases}A=b^2-3ac\\B=bc-9ad\\C=c^2-3bd\\\Delta=B^2-4AC\end{cases}。

对于一般的一元三次方程：

注意到题面中：

该方程存在三个不同实根（根的范围在 -100 至 100 之间），且根与根之差的绝对值 \ge 1。

因此只会出现 \Delta<0 的情况，适用盛金公式 4：

x_1=\dfrac{-b-2\cos\frac{\theta}{3}\sqrt A}{3a},x_{2,3}=\dfrac{-b+(\cos\frac{\theta}{3}\pm\sqrt 3\sin\frac{\theta}{3})\sqrt A}{3a}

其中 \theta=\arccos{\dfrac{2Ab-3aB}{2\sqrt{A^3}}}。

对应代码：

#include<bits/stdc++.h>
using namespace std;
#define int long double 
signed main(){
    ios::sync_with_stdio(0);cin.tie(0);
    cout<<fixed<<setprecision(2);
    int a,b,c,d;
    cin>>a>>b>>c>>d;
    int A=b*b-3*a*c;
    int B=b*c-9*a*d;
    int C=c*c-3*b*d;
//  int D=B*B-4*A*C;
    int t=acosl((2*A*b-3*a*B)/(2*sqrtl(A*A*A)));
    int x1=(-b-(2*cosl(t/3))*sqrtl(A))/3*a;
    int x2=(-b+(cosl(t/3)+sqrtl(3)*sinl(t/3))*sqrtl(A))/3*a;
    int x3=(-b+(cosl(t/3)-sqrtl(3)*sinl(t/3))*sqrtl(A))/3*a;
    cout<<min({x1,x2,x3})<<" "<<x1+x2+x3-min({x1,x2,x3})-max({x1,x2,x3})<<" "<<max({x1,x2,x3});
    return 0;
}

然而，本题是 NOIP2001 提高组的题，除非你是范盛金本人，否则你不太可能在考场看到这道题的时候在自己的记忆中找到这样的公式。所以接下来介绍第二简便的方法，暴力枚举。

还是题面中的那句话：

该方程存在三个不同实根（根的范围在 -100 至 100 之间），且根与根之差的绝对值 \ge 1。

因此我们可以直接从 -100 枚举到 100，步长定为 0.001，如果该点函数值十分接近 0 则输出保留两位小数后的结果并将当前数加上 0.5。循环最多进行 200\div0.001=200000 次，即使是那个时候的评测机也可以通过。

对应代码（同样也是十九行）：

#include<bits/stdc++.h>
using namespace std;
#define int long double
int a,b,c,d;
bool check(int x){
    return fabsl(x*x*x*a+x*x*b+x*c+d)<1e-5;
}
signed main(){
    ios::sync_with_stdio(0);cin.tie(0);
    cout<<fixed<<setprecision(2);
    cin>>a>>b>>c>>d;
    for(int x=-100;x<=100;x+=0.001){
        if(check(x)){
            cout<<x<<" ";
            x+=0.5;
        }
    }
    return 0;
}

如果你闲得慌，也可以去使用那些看起来高级一点、更快的算法，或者用 C++ 的 complex 实现复数运算从而套用卡尔丹公式，但是对于这题来说，没必要。