题意

给出三次方程

题目保证它在 $[-100,100]$ 内有三个互不相同的实根，而且任意两根的距离至少为 $1$。要求按从小到大的顺序输出三个根，并保留两位小数。

思路

为什么可以按整数区间扫描

根之间至少相距 $1$，所以每个开区间 $(i,i+1)$ 内至多有一个非整数根。

这里必须注意：不能说闭区间 $[i,i+1]$ 内一定至多有一个根。例如 $i$ 和 $i+1$ 可以恰好都是根。正确的处理方式是把两类根分开：

• 整数根在它作为区间左端点时记录；
• 非整数根在开区间 $(i,i+1)$ 内通过函数值变号找到；
• 扫描只让 $i$ 取 $-100$ 到 $99$，因此最后单独检查右端点 $100$。

三次方程有三个互异实根，设为 $r_1<r_2<r_3$，则

每个根都只出现一次，是单根。$x$ 经过某个根时，对应的因子 $x-r_k$ 改变符号，另外两个因子的符号在附近不变，所以 $f(x)$ 一定改变符号。

因此，如果非整数根 $r$ 位于 $(i,i+1)$，就一定有：

这样扫描所有整数端点，就能隔离出全部非整数根。

在变号区间内二分

找到满足 $f(l)f(r)<0$ 的区间后，取中点 $m=(l+r)/2$：

• 若 $f(l)f(m)\leqslant 0$，根在 $[l,m]$，令 $r=m$；
• 否则根在 $[m,r]$，令 $l=m$。

每次二分都保留一个含根区间，并把区间长度缩小一半。初始区间长度为 $1$，精确实数运算下二分 $80$ 次后长度为 $2^{-80}$；实际 double / float 会先到达机器精度，但这仍远高于保留两位小数所需的精度。

实现细节

多项式使用霍纳法计算：

它只需要三次乘法，写法也比直接计算 $x^2,x^3$ 更紧凑。

判断整数端点时不能直接使用固定的绝对 EPS：把方程所有系数同时乘一个很小的数不会改变根，却会让所有函数值一起变小。代码先用各项绝对值之和估计当前求值规模：

再判断 $|f(x)|\leqslant EPS\cdot S(x)$，使端点判零不受方程整体缩放影响。

判断区间是否变号之前，左右端点都要做这次判零。若右端点已经近似为整数根，就不能因为它残留的微小正负号而对当前区间执行二分；程序跳过这个区间，等下一轮让该整数成为左端点时再记录。这样每个整数根只记录一次。输出前把绝对值小于 0.0005 的结果改成 0.0，避免由逼近误差得到 -0.00。

正确性说明

1. 对任意整数根，$-100$ 到 $99$ 会在它作为左端点时记录它，根 $100$ 由最后一次检查记录；右端点判零会阻止它被前一个区间的二分提前重复记录，因此整数根不会遗漏或重复。
2. 对任意非整数根 $r$，它唯一属于某个 $(i,i+1)$。互异根都是单根，所以 $f(i)$ 与 $f(i+1)$ 异号，扫描一定会找到这个区间。
3. 二分过程中区间两端始终异号或其中一端为零，因此区间始终包含该根；区间长度不断减半，最终得到足够精确的近似值。
4. 扫描方向从左到右，整数根和区间内根也都按所在位置加入，所以输出顺序天然递增。

综上，算法会按顺序找到且只找到三个实根。

brute.py 使用 60 位 Decimal 和 180 次二分作为高精度参考程序。它用于随机对拍，不是另一种更快的提交算法，因此正文不重复嵌入。

Python 知识

固定次数的浮点二分

Python 的 float 与 C++ 的 double 一样，通常是 IEEE 754 双精度浮点数。数值二分可以直接执行固定次数，不必用 while right - left > eps 反复判断终止条件；固定次数也更容易估算误差。

半开 range 与端点处理

range(-100, 100) 依次产生 $-100,-99,\ldots,99$，恰好让每次扫描的区间是 [integer, integer + 1]。由于右端点 100 不会成为下一轮的左端点，代码在循环后单独检查它。

格式化与展开输出

f"{root:.2f}" 把一个根格式化为两位小数字符串。表达式

1print(*(f"{root:.2f}" for root in roots))

先按需产生三个字符串，再用 * 展开为 print 的参数，默认以空格分隔。

C++ 到 Python 对照

• C++ 的 fabs(x) 对应 Python 的 abs(x)。
• C++ 的 vector<double> 对应 Python 的列表。
• C++ 的 fixed << setprecision(2) 对应 Python 的 f"{value:.2f}"。
• 两种语言都使用同一个霍纳法函数和相同的二分区间更新规则。

模仿清单

1. 用 range(left, right) 扫描整数左端点，循环后单独处理最终右端点。
2. 浮点二分执行固定次数，并始终维护“答案仍在区间中”的不变量。
3. 用霍纳法计算多项式，减少乘法和中间量。
4. 固定小数位输出前处理接近零的负数，避免 -0.00。

相关 Python 笔记：

• /home/rainboy/mycode/hugo-blog/content/program_language/python/math_tools.md：浮点误差、相对/绝对误差与 Fraction / 高精度参考程序的使用边界。
• /home/rainboy/mycode/hugo-blog/content/program_language/python/oj_input_output_cheatsheet.md：浮点格式化、数组展开和常见 OJ 输入输出写法。
• /home/rainboy/mycode/hugo-blog/content/program_language/python/generator_expression.md：生成器表达式的惰性产生与一次性消费。

代码

C++17 正解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-07-19 09:46
 * update_at: 2026-07-19 10:29
 */
#include <bits/stdc++.h>
using namespace std;

const double EPS = 1e-10;

double coefficient_a, coefficient_b, coefficient_c, coefficient_d;

double polynomial(double x) {
    return ((coefficient_a * x + coefficient_b) * x + coefficient_c) * x + coefficient_d;
}

bool is_zero_at(double x, double value) {
    double absolute_x = fabs(x);
    double scale = ((fabs(coefficient_a) * absolute_x + fabs(coefficient_b)) * absolute_x
                    + fabs(coefficient_c)) * absolute_x + fabs(coefficient_d);
    return fabs(value) <= EPS * scale;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> coefficient_a >> coefficient_b >> coefficient_c >> coefficient_d;

    vector<double> roots;

    for (int integer = -100; integer < 100; integer++) {
        double left = integer;
        double right = integer + 1;
        double left_value = polynomial(left);
        double right_value = polynomial(right);
        bool left_is_root = is_zero_at(left, left_value);
        bool right_is_root = is_zero_at(right, right_value);

        // 整数根只在它作为左端点时记录；右端点根留到下一轮。
        if (left_is_root) {
            roots.push_back(left);
        } else if (!right_is_root && left_value * right_value < 0) {
            for (int iteration = 1; iteration <= 80; iteration++) {
                double middle = (left + right) / 2;
                double middle_value = polynomial(middle);

                if (left_value * middle_value <= 0) {
                    right = middle;
                } else {
                    left = middle;
                    left_value = middle_value;
                }
            }
            roots.push_back((left + right) / 2);
        }
    }

    double right_endpoint_value = polynomial(100.0);
    if (is_zero_at(100.0, right_endpoint_value)) {
        roots.push_back(100.0);
    }

    cout << fixed << setprecision(2);
    for (int i = 0; i < 3; i++) {
        double root = roots[i];
        if (fabs(root) < 0.0005) root = 0.0;
        if (i > 0) cout << ' ';
        cout << root;
    }
    cout << '\n';

    return 0;
}

Python 正解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40a, b, c, d = map(float, input().split())
EPS = 1e-10


def polynomial(x):
    return ((a * x + b) * x + c) * x + d


def is_zero_at(x, value):
    absolute_x = abs(x)
    scale = ((abs(a) * absolute_x + abs(b)) * absolute_x + abs(c)) * absolute_x + abs(d)
    return abs(value) <= EPS * scale


roots = []
for integer in range(-100, 100):
    left, right = float(integer), float(integer + 1)
    left_value, right_value = polynomial(left), polynomial(right)
    left_is_root = is_zero_at(left, left_value)
    right_is_root = is_zero_at(right, right_value)

    if left_is_root:
        roots.append(left)
    elif not right_is_root and left_value * right_value < 0:
        for _ in range(80):
            middle = (left + right) / 2
            middle_value = polynomial(middle)
            if left_value * middle_value <= 0:
                right = middle
            else:
                left = middle
                left_value = middle_value
        roots.append((left + right) / 2)

right_endpoint_value = polynomial(100.0)
if is_zero_at(100.0, right_endpoint_value):
    roots.append(100.0)

roots = [0.0 if abs(root) < 0.0005 else root for root in roots]
print(*(f"{root:.2f}" for root in roots))

复杂度

设扫描范围内有 $B=200$ 个单位区间，根的数量为 $K=3$，每个变号区间二分 $I=80$ 次。

• 时间复杂度为 $O(B+KI)$，在本题固定范围下就是 $O(1)$。
• 保存三个根，空间复杂度为 $O(K)=O(1)$。

总结

本题的关键不是盲目缩小步长，而是先利用“根间距至少为 $1$”把根隔离到整数端点或开单位区间中。三个互异实根都是单根，所以非整数根必然让区间两端函数值异号；找到变号区间后，再用固定次数二分获得足够精度。

实现时还要完整处理整数根、右端点 $100$ 和 -0.00。这些边界决定了程序能否稳定找到恰好三个根。