[C++] 一元二次方程

发表于 更新于 分类于

洛谷 P9750

众所周知，对一元二次方程 ax2 + bx + c = 0, (a ≠ 0)，可以用以下方式求实数解：

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

例如：

  • x2 + x + 1 = 0 无实数解，因为 Δ = 12 − 4 × 1 × 1 = −3 < 0。
  • x2 − 2x + 1 = 0 有两相等实数解 x1, 2 = 1。
  • x2 − 3x + 2 = 0 有两互异实数解 x1 = 1, x2 = 2。

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

题目描述

现在给定一个一元二次方程的系数 a, b, c，其中 a, b, c 均为整数且 a ≠ 0。你需要判断一元二次方程 ax2 + 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。

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

  1. 若 Δ = b2 − 4ac < 0，则表明方程无实数解，此时你应当输出 NO；

  2. 否则 Δ ≥ 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 使 d2 ∣ r（即 r 不应是 d2 的倍数）；

    此时：

    1. 若 q1 ≠ 0，则按有理数的格式输出 q1，并再输出一个加号 +；
    2. 否则跳过这一步输出；

    随后：

    1. 若 q2 = 1，则输出 sqrt({r})；
    2. 否则若 q2 为整数，则输出 {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

1
2
3
4
5
6
7
8
9
10
9 1000
1 -1 0
-1 -1 -1
1 -2 1
1 5 4
4 4 1
1 0 -432
1 -3 1
2 -4 1
1 7 1

输出 #1

1
2
3
4
5
6
7
8
9
1
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 ≤ T ≤ 5000，1 ≤ M ≤ 103，|a|,|b|,|c| ≤ M，a ≠ 0。

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

其中：

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

题解

这题相当的麻烦啊，要考虑很多边缘情况，比如若求得结果为

$$ x = \frac {a} {b} + \frac {c \sqrt{d}} {e} $$

要考虑 a = 0、b = 1、c = 0、c = 1、d = 1、e = 1 等等，都要做特判

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
#include <bits/stdc++.h>
using namespace std;

const int gcd(int a, int b){
    a = abs(a);
    b = abs(b);
    return b?gcd(b, a%b):a;
}

const pair<const int, const int> decimalSqrt(int x){
    if(!x) return {0, 1};
    int i = 2, a = x>0?1:-1, b = 1;
    map<int, int> Map;
    if(x<0) x = -x;
    while(x!=1){
        while(!(x%i)){
            x /= i;
            Map[i]++;
        }
        i++;
    }
    for(auto& j : Map){
        a *= pow(j.first, j.second/2);
        if(j.second&1) b *= j.first;
    }
    return {a, b};
}

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

    int t, m;
    cin >> t >> m;

    while(t--){
        int a, b, c;
        cin >> a >> b >> c;

        int delta = b*b - 4*a*c;
        if(delta<0){
            cout << "NO" << endl;
            continue;
        }

        b = -b;
        const auto& sd = decimalSqrt(delta);
        if(sd.second == 1){
            b += a<0?-sd.first:sd.first;
        }

        if(b){
            if(b%(2*a)){
            int g = gcd(b, 2*a);
            cout << (((b<0)^(a<0))?"-":"") << abs(b/g) << "/" << abs(2*a/g);
            }else cout << b/(2*a);
        }


        if(sd.second!=1){
            if(b) cout << "+";

            int h = gcd(sd.first, 2*a);
            int i = abs(sd.first/h);

            if(i!=1) cout << i << "*";

            cout << "sqrt(" << sd.second << ")";

            if(sd.first%(2*a)) cout << "/" << abs(2*a/h);
        }

        if(!b && sd.second==1) cout << 0;

        cout << endl;
    }
    return 0;
}