2023年CSP-J T3一元二次方程

阅读量: 467 编辑

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

计算 Δ=b2 − 4ac,则:

1、若 Δ < 0,则该一元二次方程无实数解。

2、否则 Δ≥0,此时该一元二次方程有两个实数解 x1,2 = (−b±√Δ)/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 时须遵循以下规则:

1、由有理数的定义,存在唯一的两个整数 p 和 q,满足 q>0,gcd(p, q) = 1 且 v = p/q。

2、若 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 = q1 + q2√r 的形式,其中:

    • q1, q2 为有理数,且 q2 > 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) 否则若 q3 为整数,则输出 sqrt({r})/{q3};

  • (4) 否则可以证明存在唯一整数 c, d 满足 c, d > 1, gcd(c, d) = 1 且 q2 = c/d,此时输出 {c}*sqrt({r})/{d};

上述表示中 {n} 代表整数 {n} 的值,详见样例。

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

【输入格式】

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

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

数据范围:1≤T≤5000,1≤M≤1000,|a|,|b|,|c| ≤ M,a ≠ 0

【输出格式】

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

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

【输入样例】

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
NO
1
-1
-1/2
12*sqrt(3)
3/2+sqrt(5)/2
1+sqrt(2)/2
-7/2+3*sqrt(5)/2

【参考程序】

// 爱码岛编程 P9750
#include <bits/stdc++.h>
using namespace std;

// 求最大公约数 __gcd(p, q)  p/q
int gcd(int p, int q) {
    int t = 0;
    while (q != 0) {
        t = p % q;
        p = q;
        q = t;
    }
    return p;
}

// p/q
void fun1(int p, int q) {
    if (p * q < 0) {
        cout << "-";
    }
    if (p < 0) p = -p;
    if (q < 0) q = -q;
    int g = gcd(p, q);
    if (q == g) {
        cout << p / g;
    } else {
        cout << p / g << "/" << q / g;
    }
}

// q/q  sqrt
void fun2(int p, int q) {
    if (q < 0) q = -q;
    int t = 1;
    for (int i = sqrt(p); i >= 2; i--) {
        if (p % (i * i) == 0) {
            p = p / (i * i);
            t = t * i;
            break;
        }
    }
    int g = gcd(t, q);
    t = t / g;
    q = q / g;
    if (t != 1) {
        cout << t << "*";
    }
    if (p != 1) {
        cout << "sqrt(" << p << ")";
    }
    if (q != 1) {
        cout << "/" << q;
    }
}

int T, M, a, b, c;
int main() {
    cin >> T >> M;
    while (T--) {
        cin >> a >> b >> c;
        int delta = b * b - 4 * a * c;
        if (delta < 0) {
            cout << "NO";
        } else {
            int d = sqrt(delta);
            if (d * d == delta) {
                double x1 = (-b + d) / 2.0 * a;
                double x2 = (-b - d) / 2.0 * a;

                if (x1 >= x2) {
                    if (-b + d == 0) {
                        cout << 0;
                    } else {
                        fun1(-b + d, 2 * a);
                    }
                } else {
                    if (-b - d == 0) {
                        cout << 0;
                    } else {
                        fun1(-b - d, 2 * a);
                    }
                }
            } else {
                if (b != 0) {
                    fun1(-b, 2 * a);
                    cout << "+";
                }
                fun2(delta, 2 * a);
            }
        }

        cout << endl;
    }

    return 0;
}
爱码岛编程公众号
试卷资料
爱码岛编程小程序
在线刷题
苏ICP备13052010号
©2023 南京匠成信息科技有限公司