2023 一元二次方程 · 方案一照公式逐步写

CSP-J 标程 · 复赛真题 · 代码 · cpp · 难度 3/5 · 共 2516 字
统一符号、判判别式、提平方因子
2023
数学
正文

// CSP-J 2023 复赛 T3 · 一元二次方程
// 原题：https://oj.yecheng.tv/p/CSPJ2023C
// 题意：解 a*x^2 + b*x + c = 0，取较大的那个实根，按题目规定的格式输出；无实根输出 NO。
// 格式要点：有理数写成最简分数（分母为 1 就只写分子）；
// 无理根写成「有理部分 + 系数 * sqrt(无平方因子部分)」，系数为 1 时省略。
//
// 方案一 · 一步一步照着公式写
// 第一步 统一符号：若 a < 0，把方程两边同乘 -1（a、b、c 全变号）。
//   这样 a 一定是正数，较大根就固定是 (-b + sqrt(delta)) / (2a)，不用再分情况讨论。
// 第二步 算判别式 delta = b^2 - 4ac，小于 0 直接 NO。
// 第三步 开方：先判 delta 是不是完全平方数。
//   · 是：根是有理数 (-b + sqrt(delta)) / (2a)，约分后输出；
//   · 否：把 delta 里的平方因子全部提出来，写成 delta = s^2 * r（r 不再含任何平方因子），
//         于是 根 = (-b)/(2a) + (s/(2a)) * sqrt(r)，两部分各自约分后按格式拼起来。
// 开方一律用「先估后校」：sqrtl 估一下，再用 while 往回收一收，避免浮点误差。

#include <bits/stdc++.h>
using namespace std;

void printRational(long long p, long long q) {
    if (q < 0) {
        p = -p;
        q = -q;
    }
    long long g = std::gcd(llabs(p), q);
    p /= g;
    q /= g;
    if (q == 1) cout << p;
    else cout << p << "/" << q;
}

long long isqrtFloor(long long x) {
    long long s = (long long)sqrtl((long double)x);
    while (s * s > x) s--;
    while ((s + 1) * (s + 1) <= x) s++;
    return s;
}

int main() {
    freopen("uqe.in", "r", stdin);
    freopen("uqe.out", "w", stdout);

    int T, M;
    cin >> T >> M;
    while (T--) {
        long long a, b, c;
        cin >> a >> b >> c;
        if (a < 0) {
            a = -a;
            b = -b;
            c = -c;
        }
        long long delta = b * b - 4 * a * c;
        if (delta < 0) {
            cout << "NO\n";
            continue;
        }

        long long p1 = -b;          // 有理部分的分子
        long long q1 = 2 * a;       // 有理部分的分母（a > 0，所以分母为正）

        long long sq = isqrtFloor(delta);
        if (sq * sq == delta) {     // 判别式是完全平方数，两个根都是有理数
            printRational(p1 + sq, q1);
            cout << "\n";
            continue;
        }

        long long s = 1, r = delta; // 提平方因子：delta = s^2 * r
        for (long long i = 2; i * i <= r; i++) {
            while (r % (i * i) == 0) {
                r /= i * i;
                s *= i;
            }
        }

        long long p2 = s, q2 = 2 * a;
        long long g2 = std::gcd(p2, q2);
        p2 /= g2;
        q2 /= g2;

        if (p1 != 0) {
            printRational(p1, q1);
            cout << "+";
        }
        if (p2 == 1 && q2 == 1) cout << "sqrt(" << r << ")";
        else if (q2 == 1) cout << p2 << "*sqrt(" << r << ")";
        else if (p2 == 1) cout << "sqrt(" << r << ")/" << q2;
        else cout << p2 << "*sqrt(" << r << ")/" << q2;
        cout << "\n";
    }
    return 0;
}
2023 一元二次方程 · 方案一 照公式逐步写

正文

CSP-J 标程 · 复赛真题的其它内容

2023 一元二次方程 · 方案一照公式逐步写
