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

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

按判别式分类讨论，先约分有理部分，再把判别式开方后提取最大平方因子并格式化输出较大实根。

OJ: luogu

题目 ID: P9750

难度:普及-

标签:数学模拟推导

日期: 2026-06-18 21:42

题意

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

如果没有实数解，输出 NO；
如果有实数解，只输出两个实数解中较大的那个。

输出格式不能随便写小数，而要按题目要求写成：

最简整数或分数；
或者 $q1 + q2*sqrt(r)$ 这种根式形式，其中 q2 > 0，r 里不能再含平方因子。

思路

先看一个可以直接验证想法的朴素解：

先算判别式 $Delta = b^2 - 4ac$ 。如果 Delta < 0，直接无解。
如果 Delta 是完全平方数，较大根就是一个有理数，只要约分即可。
如果 Delta 不是完全平方数，就直接枚举 Delta 的最大平方因子，把 sqrt(Delta) 化成 $d*sqrt(r)$ 。

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// brute.cpp：小数据暴力解，用来帮助理解题意并辅助对拍。
#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);
}

// 暴力枚举最大的平方因子 best^2，使得 best^2 | delta。
void extract_square_part_bruteforce(ll delta, ll &square_part, ll &rest) {
    square_part = 1;
    for (ll d = 1; d * d <= delta; d++) {
        ll sq = d * d;
        if (delta % sq == 0) {
            square_part = d;
        }
    }
    rest = delta / (square_part * square_part);
}

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);
    }

    Fraction q1 = make_fraction(-b, 2 * a);

    ll square_part, rest;
    extract_square_part_bruteforce(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;
}

这题真正容易错的不是复杂度，而是格式和符号。

为了统一“较大根”的写法，可以把答案写成：

$-b / (2a) + sqrt(Delta) / (2|a|)$

这样根号项前面的系数天然为正，正好满足题目要求里的 q2 > 0。

接下来只要把 Delta 分解成：

$Delta = s^2 * r$

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

$q1 + q2 * sqrt(r)$

其中：

$q1 = -b / (2a)$
$q2 = s / (2|a|)$

最后分别把 q1、q2 约成最简分数，再根据题目给出的四种格式输出即可。

代码

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)$ 。
在本题的数据范围内，这个复杂度完全够用。

总结

这题本质是数学化简题：

用判别式判断有没有实数解；
用统一公式锁定较大根；
把分数约分；
把根号里的平方因子提出去；
按题目规定格式输出。

只要把这几步拆清楚，实现并不复杂。

一图流解析

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

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：如果方程有解，那么方程的两个解都是整数。

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

目录

题意

思路

代码

复杂度

总结

一图流解析