[CSP-J 2023] 一元二次方程

GitHub跳转原题关系图返回列表

把较大根统一成 -b/(2a)+sqrt(Delta)/(2|a|)，再用质因数分解或倒序枚举两种方式提净判别式里的平方因子并格式化输出。

OJ: luogu

题目 ID: P9750

难度:普及-

标签:数学模拟推导

创建: 2026-06-18 21:42

更新: 2026-10-07 12:15

前置题目

roj 1210因子分解A 教的从 2 试除并用 while 除尽统计指数的分解法，正是 B 解法一提取平方因子时对 Δ 试除分解的原样实现，B 只是额外按指数奇偶拆出 s²·r

形式化题目

给出 $T$ 组整系数一元二次方程 $ax^2 + bx + c = 0$ ，其中 $a \neq 0$ 。对每组方程：

判别式 $\Delta = b^2 - 4ac$ 为负时方程无实数解，输出 NO；
否则输出两个实数解中较大的那个，并且必须写成题面规定的两种形式之一：
- 最简有理数 $v = p/q$ ，其中 $q > 0$ 、 $\gcd(p, q) = 1$ ， $q = 1$ 时只写 $p$ ；
- 根式 $q_1 + q_2\sqrt{r}$ ，其中 $q_2 > 0$ ， $r > 1$ 且不含平方因子（不存在 $d > 1$ 使 $d^2 \mid r$ ）， $q_1 = 0$ 时省略有理部分和它后面的加号。

这题真正容易错的不是复杂度，而是格式和符号：根号项系数必须为正、 $r$ 必须提净平方因子、分数必须约到最简。

解法总览

两种解法共享同一套化简骨架：

用判别式判断有没有实数解；
把较大根统一写成 $-b/(2a) + \sqrt{\Delta}/(2|a|)$ ，让根号项前面的系数天然为正，正好满足 $q_2 > 0$ ；
把 $\Delta$ 拆成 $s^2 \cdot r$ ，其中 $r$ 不再含平方因子；
$q_1 = -b/(2a)$ 、 $q_2 = s/(2|a|)$ 各自约成最简分数，再按题面四种格式输出。

差别只在第 3 步怎么把 $\Delta$ 拆成 $s^2 \cdot r$ ：

解法一（main.cpp，正式主解）：分解质因数，按指数的奇偶分拣平方因子；
解法二（main2.cpp）：完全不分解，整数二分求出 $\lfloor\sqrt{\Delta}\rfloor$ 后从大到小枚举 $s$ ，第一个整除 $\Delta$ 的就是最大平方因子。

两个解法输入输出格式相同、结论一致，属于替代关系而不是层层优化。同目录的 brute.cpp 是解法二思路的朴素版本：从小到大枚举所有 $d$ 并记录最大命中者，只用来对拍。

解法一：分解质因数提取平方因子

思路

先算判别式 $\Delta = b^2 - 4ac$ ：

$\Delta$ 为负，直接输出 NO；
$\Delta$ 是完全平方数，较大根一定是有理数，代入公式约分即可；
否则较大根是无理数，走根式格式。

把较大根统一写成：

-b/(2a) + \sqrt{\Delta}/(2|a|)

这样根号项前面的系数恒为正，天然满足题目要求的 $q_2 > 0$ ，不用再分 $a$ 的正负讨论根号项符号。

接下来把 $\Delta$ 分解质因数，写成：

\Delta = s^2 \cdot r

其中 $r$ 不再含平方因子，那么答案就能写成：

q_1 + q_2\sqrt{r}

其中：

$q_1 = -b/(2a)$
$q_2 = s/(2|a|)$

最后分别把 $q_1$ 、 $q_2$ 约成最简分数，再按题面四种格式输出： $q_2$ 是 $1$ 只写 sqrt(r)，是整数写 c*sqrt(r)，倒数是整数写 sqrt(r)/d，否则写 c*sqrt(r)/d。

代码

cpp

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
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132#include <bits/stdc++.h>
using namespace std;

using ll = long long;

struct Fraction {
    ll num, den;
};

int T, M;
ll a, b, c;

ll gcd_ll(ll x, ll y) {
    if (x < 0) x = -x;
    if (y < 0) y = -y;
    while (y != 0) {
        ll t = x % y;
        x = y;
        y = t;
    }
    return x;
}

ll abs_ll(ll x) {
    return x >= 0 ? x : -x;
}

// 把分数化成最简形式，并保证分母为正。
Fraction make_fraction(ll num, ll den) {
    if (den < 0) {
        num = -num;
        den = -den;
    }
    ll g = gcd_ll(num, den);
    num /= g;
    den /= g;
    return {num, den};
}

string fraction_to_string(Fraction x) {
    if (x.den == 1) {
        return to_string(x.num);
    }
    return to_string(x.num) + "/" + to_string(x.den);
}

// 把 delta 分解成 square_part^2 * rest，其中 rest 为平方因子已经提干净后的数。
void extract_square_part(ll delta, ll &square_part, ll &rest) {
    square_part = 1;
    rest = 1;

    ll x = delta;
    for (ll p = 2; p * p <= x; p++) {
        if (x % p != 0) {
            continue;
        }
        int cnt = 0;
        while (x % p == 0) {
            x /= p;
            cnt++;
        }
        for (int i = 0; i < cnt / 2; i++) {
            square_part *= p;
        }
        if (cnt % 2 == 1) {
            rest *= p;
        }
    }
    if (x > 1) {
        rest *= x;
    }
}

string radical_term_to_string(Fraction coef, ll rest) {
    if (coef.den == 1) {
        if (coef.num == 1) {
            return "sqrt(" + to_string(rest) + ")";
        }
        return to_string(coef.num) + "*sqrt(" + to_string(rest) + ")";
    }

    if (coef.num == 1) {
        return "sqrt(" + to_string(rest) + ")/" + to_string(coef.den);
    }
    return to_string(coef.num) + "*sqrt(" + to_string(rest) + ")/" + to_string(coef.den);
}

string solve_one() {
    ll delta = b * b - 4 * a * c;
    if (delta < 0) {
        return "NO";
    }

    ll sq = (ll) sqrtl((long double) delta);
    while ((sq + 1) * (sq + 1) <= delta) sq++;
    while (sq * sq > delta) sq--;

    // 判别式是完全平方数时，答案一定是有理数。
    if (sq * sq == delta) {
        ll num = -b + (a > 0 ? sq : -sq);
        Fraction ans = make_fraction(num, 2 * a);
        return fraction_to_string(ans);
    }

    // 较大实根统一写成 -b/(2a) + sqrt(delta)/(2|a|)，这样根号项系数恒为正。
    Fraction q1 = make_fraction(-b, 2 * a);

    ll square_part, rest;
    extract_square_part(delta, square_part, rest);
    Fraction q2 = make_fraction(square_part, 2 * abs_ll(a));

    string res;
    if (q1.num != 0) {
        res += fraction_to_string(q1);
        res += "+";
    }
    res += radical_term_to_string(q2, rest);
    return res;
}

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

    cin >> T >> M;
    while (T--) {
        cin >> a >> b >> c;
        cout << solve_one() << '\n';
    }

    return 0;
}

复杂度

设判别式为 $\Delta$ ，单组数据分解质因数的时间复杂度是 $O(\sqrt{\Delta})$ ，空间复杂度是 $O(1)$ 。本题 $\Delta \leqslant 5 \times 10^6$ ，最坏约两千多次试除， $T = 5000$ 时完全够用。

解法二：倒序枚举提取平方因子

思路

统一公式沿用解法一，区别只在第 3 步：不分解质因数，而是直接枚举 $s$ 。

用整数二分求出 $s_0 = \lfloor\sqrt{\Delta}\rfloor$ ，不用 (long double) sqrt，避开浮点数在完全平方数边界上的舍入误差；
从 $s = s_0$ 开始往下枚举，第一个使 $s^2$ 整除 $\Delta$ 的 $s$ 就是最大平方因子，令 $r = \Delta / s^2$ ；都不整除时 $s = 1$ 。

正确性很直接：题目要的 $s$ 就是满足 $s^2 \mid \Delta$ 的最大值，倒序枚举第一次命中即为最大；起点取 $\lfloor\sqrt{\Delta}\rfloor$ 保证不会漏掉更大的 $s$ （ $s > \lfloor\sqrt{\Delta}\rfloor$ 时 $s^2 > \Delta$ ，不可能整除）。

由于 $\Delta \leqslant 5 \times 10^6$ ，有 $\lfloor\sqrt{\Delta}\rfloor \leqslant 2237$ ，最坏也就枚举两千多次，与解法一同阶，换来的是更短的代码和纯整数运算。

代码

cpp

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
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139/**
 * 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-10-02 08:45
 * update_at: 2026-10-02 08:45
 */
// main2.cpp：第二种解法。整数二分求 sqrt(delta)，再从大到小枚举平方因子提根号，
// 不分解质因数、不用浮点开方，最后按题面格式输出较大实根。
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

struct Fraction {
    ll num, den;
};

int T, M;
ll a, b, c;

ll gcd_ll(ll x, ll y) {
    if (x < 0) x = -x;
    if (y < 0) y = -y;
    while (y != 0) {
        ll t = x % y;
        x = y;
        y = t;
    }
    return x;
}

// 把分数约成最简形式，并保证分母为正。
Fraction make_fraction(ll num, ll den) {
    if (den < 0) {
        num = -num;
        den = -den;
    }
    ll g = gcd_ll(num, den);
    num /= g;
    den /= g;
    return {num, den};
}

string fraction_to_string(Fraction x) {
    if (x.den == 1) {
        return to_string(x.num);
    }
    return to_string(x.num) + "/" + to_string(x.den);
}

// 整数开方：返回最大的 s 满足 s * s <= x（x >= 0）。
// 二分求解，避免 (long double) sqrt 舍入带来的边界误差。
ll isqrt(ll x) {
    ll left = 0;
    ll right = 1;
    while (right * right <= x) {
        right *= 2;
    }
    ll answer = 0;
    while (left <= right) {
        ll mid = left + (right - left) / 2;
        if (mid * mid <= x) {
            answer = mid;
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    return answer;
}

// 从大到小枚举 s，第一个满足 s * s 整除 delta 的 s 就是最大平方因子，
// 于是 delta = s * s * r，且 r 中不再含平方因子。
// delta = b*b - 4ac <= 10^6 + 4 * 10^6 = 5 * 10^6，所以 s 最多枚举到 2237 左右。
ll max_square_factor(ll delta) {
    for (ll s = isqrt(delta); s >= 1; s--) {
        if (delta % (s * s) == 0) {
            return s;
        }
    }
    return 1;
}

// 根号项的四种输出格式：1、整数、1/q、c/q（约分后 c、q 互质）。
string radical_term_to_string(Fraction coef, ll rest) {
    if (coef.den == 1) {
        if (coef.num == 1) {
            return "sqrt(" + to_string(rest) + ")";
        }
        return to_string(coef.num) + "*sqrt(" + to_string(rest) + ")";
    }
    if (coef.num == 1) {
        return "sqrt(" + to_string(rest) + ")/" + to_string(coef.den);
    }
    return to_string(coef.num) + "*sqrt(" + to_string(rest) + ")/" + to_string(coef.den);
}

string solve_one() {
    ll delta = b * b - 4 * a * c;
    if (delta < 0) {
        return "NO";
    }

    ll sq = isqrt(delta);
    // 判别式是完全平方数时，较大根一定是有理数，直接约分输出。
    if (sq * sq == delta) {
        ll num = -b + (a > 0 ? sq : -sq); // a < 0 时分母为负，取 -sq 让根号项仍为正
        return fraction_to_string(make_fraction(num, 2 * a));
    }

    // 较大根统一写成 -b/(2a) + sqrt(delta)/(2|a|)，这样根号项系数恒为正，
    // 正好满足题目要求的 q2 > 0。
    Fraction q1 = make_fraction(-b, 2 * a);

    ll s = max_square_factor(delta); // delta = s * s * r
    Fraction q2 = make_fraction(s, 2 * (a > 0 ? a : -a));

    string res;
    if (q1.num != 0) { // q1 = 0 时按题面跳过有理数部分，直接写根号项
        res += fraction_to_string(q1);
        res += "+";
    }
    res += radical_term_to_string(q2, delta / (s * s));
    return res;
}

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

    cin >> T >> M;
    while (T--) {
        cin >> a >> b >> c;
        cout << solve_one() << '\n';
    }

    return 0;
}

复杂度

单组数据的时间复杂度是 $O(\sqrt{\Delta})$ （最坏从 $s_0$ 一路枚举到 $1$ ），空间复杂度是 $O(1)$ 。

复杂度对比

解法	提平方因子的方式	单组时间	空间	特点
解法一 `main.cpp`	分解质因数	$O(\sqrt{\Delta})$	$O(1)$	正式主解，按指数奇偶分拣，思路通用
解法二 `main2.cpp`	倒序枚举	$O(\sqrt{\Delta})$	$O(1)$	纯整数、无分解，命中大平方因子时更早结束

两者同阶，任选其一都能通过；差别主要在写法长短和是否依赖浮点开方。

总结

这题本质是数学化简题：

用判别式判断有没有实数解；
用统一公式 $-b/(2a) + \sqrt{\Delta}/(2|a|)$ 锁定较大根；
把分数约分；
把根号里的平方因子提干净；
按题目规定格式输出。

第 4 步可以用质因数分解做，也可以直接倒序枚举做，两种写法都只要 $O(\sqrt{\Delta})$ 。只要把这几步拆清楚，实现并不复杂。

图示解析

这张图把本题的建模、关键转移、实现检查和训练方法压缩到一页，适合读完正文后复盘。

P9750 [CSP-J 2023] 一元二次方程

题目背景

众所周知，对一元二次方程 $ax ^ 2 + bx + c = 0(a \neq 0)$ ，可以用以下方式求实数解：

计算 $\Delta = b ^ 2 - 4ac$ ，则:
1. 若 $\Delta < 0$ ，则该一元二次方程无实数解。
2. 否则 $\Delta \geq 0$ ，此时该一元二次方程有两个实数解 $x _ {1, 2} = \frac{-b \pm \sqrt \Delta}{2a}$ 。

例如：

$x ^ 2 + x + 1 = 0$ 无实数解，因为 $\Delta = 1 ^ 2 - 4 \times 1 \times 1 = -3 < 0$ 。
$x ^ 2 - 2x + 1 = 0$ 有两相等实数解 $x _ {1, 2} = 1$ 。
$x ^ 2 - 3x + 2 = 0$ 有两互异实数解 $x _ 1 = 1, x _ 2 = 2$ 。

在题面描述中 $a$ 和 $b$ 的最大公因数使用 $\gcd(a, b)$ 表示。例如 $12$ 和 $18$ 的最大公因数是 $6$ ，即 $\gcd(12, 18) = 6$ 。

题目描述

现在给定一个一元二次方程的系数 $a, b, c$ ，其中 $a, b, c$ 均为整数且 $a \neq 0$ 。你需要判断一元二次方程 $a x ^ 2 + bx + c = 0$ 是否有实数解，并按要求的格式输出。

在本题中输出有理数 $v$ 时须遵循以下规则：

由有理数的定义，存在唯一的两个整数 $p$ 和 $q$ ，满足 $q > 0$ ， $\gcd(p, q) = 1$ 且 $v = \frac pq$ 。
若 $q = 1$ ，则输出 {p}，否则输出 {p}/{q}，其中 {n} 代表整数 $n$ 的值；
例如：
- 当 $v = -0.5$ 时， $p$ 和 $q$ 的值分别为 $-1$ 和 $2$ ，则应输出 -1/2；
- 当 $v = 0$ 时， $p$ 和 $q$ 的值分别为 $0$ 和 $1$ ，则应输出 0。

对于方程的求解，分两种情况讨论：

若 $\Delta = b ^ 2 - 4ac < 0$ ，则表明方程无实数解，此时你应当输出 NO；
否则 $\Delta \geq 0$ ，此时方程有两解（可能相等），记其中较大者为 $x$ ，则：
1. 若 $x$ 为有理数，则按有理数的格式输出 $x$ 。
2. 否则根据上文公式， $x$ 可以被唯一表示为 $x = q _ 1 + q _ 2 \sqrt r$ 的形式，其中：
  - $q _ 1, q _ 2$ 为有理数，且 $q _ 2 > 0$ ；
  - $r$ 为正整数且 $r > 1$ ，且不存在正整数 $d > 1$ 使 $d ^ 2 \mid r$ （即 $r$ 不应是 $d ^ 2$ 的倍数）；
此时：
1. 若 $q _ 1 \neq 0$ ，则按有理数的格式输出 $q _ 1$ ，并再输出一个加号 +；
2. 否则跳过这一步输出；
随后：
1. 若 $q _ 2 = 1$ ，则输出 sqrt({r})；
2. 否则若 $q _ 2$ 为整数，则输出 {q2}*sqrt({r})；
3. 否则若 $q _ 3 = \frac 1{q _ 2}$ 为整数，则输出 sqrt({r})/{q3}；
4. 否则可以证明存在唯一整数 $c, d$ 满足 $c, d > 1, \gcd(c, d) = 1$ 且 $q _ 2 = \frac cd$ ，此时输出 {c}*sqrt({r})/{d}；
上述表示中 {n} 代表整数 {n} 的值，详见样例。

如果方程有实数解，则按要求的格式输出两个实数解中的较大者。否则若方程没有实数解，则输出 NO。

输入格式

输入的第一行包含两个正整数 $T, M$ ，分别表示方程数和系数的绝对值上限。

接下来 $T$ 行，每行包含三个整数 $a, b, c$ 。

输出格式

输出 $T$ 行，每行包含一个字符串，表示对应询问的答案，格式如题面所述。

每行输出的字符串中间不应包含任何空格。

输入输出样例 #1

输入 #1

text

输出 #1

text

1
2
3
4
5
6
7
8
91
NO
1
-1
-1/2
12*sqrt(3)
3/2+sqrt(5)/2
1+sqrt(2)/2
-7/2+3*sqrt(5)/2

说明/提示

【样例 #2】

见附件中的 uqe/uqe2.in 与 uqe/uqe2.ans。

【数据范围】

对于所有数据有： $1 \leq T \leq 5000$ ， $1 \leq M \leq 10 ^ 3$ ， $|a|,|b|,|c| \leq M$ ， $a \neq 0$ 。

测试点编号	$M \leq$	特殊性质 A	特殊性质 B	特殊性质 C
$1$	$1$	是	是	是
$2$	$20$	否	否	否
$3$	$10 ^ 3$	是	否	是
$4$	$10 ^ 3$	是	否	否
$5$	$10 ^ 3$	否	是	是
$6$	$10 ^ 3$	否	是	否
$7, 8$	$10 ^ 3$	否	否	是
$9, 10$	$10 ^ 3$	否	否	否

其中：

特殊性质 A：保证 $b = 0$ ；
特殊性质 B：保证 $c = 0$ ；
特殊性质 C：如果方程有解，那么方程的两个解都是整数。