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

思路

大模拟，按照题意模拟即可。

首先按照 $\Delta$ 的取值分为 $3$ 类：

1. $\Delta < 0$。

2. $\Delta = 0$。

3. $\Delta > 0$。

对于第 1 种情况，根据题意，输出 NO。

对于第 2 种情况，原方程只会有一个解为 $\frac{-b}{2a}$，求一个 $\gcd$ 约分即可。

对于第 3 种情况，原方程会有两个解 $\frac{-b \pm \times \sqrt{\Delta}}{2a}$，此时我们可以得到此时取 $-$ 更优，还是取 $+$ 更优。在这里我们定义 $w = -1/1$ 表示在原方程中取 $-$ / $+$ 更优。

然后化简 $\sqrt{\Delta}$ 为一个 pair t，表示 $t_1 \sqrt{t_2}$ 并且满足 $\sqrt{t_2}$ 最简。

将 $t_2$ 的取值也分为 $2$ 种情况：

1. $t_2 = 1$。

2. $t_2 \neq 1$。

对于第 1 种情况，答案为 $\frac{-b + w \times t_1}{2a}$。

对于第 2 种情况，由于 $\frac{-b}{2a}$ 有可能为 $0$，所以需要单独判断一下即可。

Code

#include <bits/stdc++.h>  
#define fst first  
#define snd second  
#define re register  
#define int long long  
#define double long double  
  
using namespace std;  
  
typedef pair<int,int> pii;  
const double eps = 1e-5;  
int T,lim,a,b,c;  
  
inline int read(){  
    int r = 0,w = 1;  
    char c = getchar();  
    while (c < '0' || c > '9'){  
        if (c == '-') w = -1;  
        c = getchar();  
    }  
    while (c >= '0' && c <= '9'){  
        r = (r << 1) + (r << 3) + (c ^ 48);  
        c = getchar();  
    }  
    return r * w;  
}  
  
inline int gcd(int a,int b){  
    if (!b) return a;  
    return gcd(b,a % b);  
}  
  
inline int qmi(int a,int b){  
    int res = 1;  
    while (b){  
        if (b & 1) res *= a;  
        a *= a;  
        b >>= 1;  
    }  
    return res;  
}  
  
inline void print_num(int x,int y,bool f){  
    if (!x){  
        if (f) printf("0");  
        return;  
    }  
    int w = 1;  
    if (x < 0){  
        x = -x;  
        w *= (-1);  
    }  
    if (y < 0){  
        y = -y;  
        w *= (-1);  
    }  
    int g = gcd(x,y);  
    x /= g;  
    y /= g;  
    if (!~w) printf("-");  
    if (y == 1) printf("%lld",x);  
    else printf("%lld/%lld",x,y);  
}  
  
inline pii get_sqrt(int x){  
    pii res = {1,1};  
    for (re int i = 2;i * i <= x;i++){  
        if (x % i == 0){  
            int cnt = 0;  
            while (x % i == 0){  
                cnt++;  
                x /= i;  
            }  
            res.fst *= qmi(i,cnt / 2);  
            res.snd *= max(1ll,i * (cnt % 2));  
        }  
    }  
    if (x != 1) res.snd *= x;  
    return res;  
}  
  
inline pii get_div(int w,bool ok,int x,int y){  
    if (x < 0){  
        x = -x;  
        w *= (-1);  
    }  
    if (y < 0){  
        y = -y;  
        w *= (-1);  
    }  
    int g = gcd(x,y);  
    x /= g;  
    y /= g;  
    if (ok){  
        if (~w) printf("+");  
        else printf("-");  
    }  
    return {x,y};  
}  
  
inline void solve(){  
    int w;  
    a = read();  
    b = read();  
    c = read();  
    int del = b * b - 4 * a * c;  
    if (del < 0){  
        puts("NO");  
        return;  
    }  
    if (!del){  
        print_num(-b,2 * a,true);  
        puts("");  
        return;  
    }  
    double sdel = sqrtl(del);  
    if ((1.0 * (-1.0 * b - sdel) / (2.0 * a)) > (1.0 * (-1.0 * b + sdel) / (2.0 * a))) w = -1;  
    else w = 1;  
    pii t = get_sqrt(del);  
    if (t.snd == 1){  
        int s = -b + w * t.fst;  
        int m = 2 * a;  
        print_num(s,m,true);  
    }  
    else{  
        double div = fabs((-b) / (2.0 * a));  
        bool ok;  
        print_num(-b,2 * a,false);  
        if (div > eps) ok = true;  
        else ok = false;  
        pii res = get_div(w,ok,t.fst,2 * a);  
        if (res.fst != 1) printf("%lld*",res.fst);  
        printf("sqrt(%lld)",t.snd);  
        if (res.snd != 1) printf("/%lld",res.snd);  
    }  
    puts("");  
}  
  
signed main(){  
    T = read();  
    lim = read();  
    while (T--) solve();  
    return 0;  
}