#765. [CSP-J2023 C] 一元二次方程

[CSP-J2023 C] 一元二次方程

题目背景

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

  • 计算 Δ=b24ac\Delta=b^2-4ac,则:
    1. Δ<0\Delta<0,则该一元二次方程无实数解。
    2. 否则 Δ0\Delta \ge 0,此时该一元二次方程有两个实数解 x1,2=b±Δ2ax _ {1, 2} = \dfrac{-b \pm \sqrt \Delta}{2a}

例如:

  • x2+x+1=0x ^ 2 + x + 1 = 0 无实数解,因为 Δ=124×1×1=3<0\Delta = 1 ^ 2 - 4 \times 1 \times 1 = -3 < 0
  • x22x+1=0x ^ 2 - 2x + 1 = 0 有两相等实数解 x1,2=1x _ {1, 2} = 1
  • x23x+2=0x ^ 2 - 3x + 2 = 0 有两互异实数解 x1=1,x2=2x _ 1 = 1, x _ 2 = 2

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

题目描述

现在给定一个一元二次方程的系数 a,b,ca, b, c,其中 a,b,ca, b, c 均为整数且 a0a \neq 0。你需要判断一元二次方程 ax2+bx+c=0a x ^ 2 + bx + c = 0 是否有实数解,并按要求的格式输出。

在本题中输出有理数 vv 时须遵循以下规则:

  • 由有理数的定义,存在唯一的两个整数 ppqq,满足 q>0q > 0gcd(p,q)=1\gcd(p, q) = 1v=pqv = \frac pq

  • q=1q = 1则输出 {p},否则输出 {p}/{q},其中 {n} 代表整数 nn 的值;

  • 例如:

    • v=0.5v = -0.5 时,ppqq 的值分别为 1-122,则应输出 -1/2
    • v=0v = 0 时,ppqq 的值分别为 0011,则应输出 0

对于方程的求解,分两种情况讨论:

  1. Δ=b24ac<0\Delta = b ^ 2 - 4ac < 0,则表明方程无实数解,此时你应当输出 NO

  2. 否则 Δ0\Delta \geq 0,此时方程有两解(可能相等),记其中较大者为 xx,则:

    1. xx 为有理数,则按有理数的格式输出 xx

    2. 否则根据上文公式,xx 可以被唯一表示为 x=q1+q2rx = q _ 1 + q _ 2 \sqrt r 的形式,其中:

      • q1,q2q _ 1, q _ 2 为有理数,且 q2>0q _ 2 > 0
      • rr 为正整数且 r>1r > 1,且不存在正整数 d>1d > 1 使 d2rd ^ 2 \mid r(即 rr 不应是 d2d ^ 2 的倍数);

    此时:

    1. q10q _ 1 \neq 0,则按有理数的格式输出 q1q _ 1,并再输出一个加号 +
    2. 否则跳过这一步输出;

    随后:

    1. q2=1q _ 2 = 1,则输出 sqrt({r})
    2. 否则若 q2q _ 2 为整数,则输出 {q2}*sqrt({r})
    3. 否则若 q3=1q2q _ 3 = \frac 1{q _ 2} 为整数,则输出 sqrt({r})/{q3}
    4. 否则可以证明存在唯一整数 c,dc, d 满足 c,d>1,gcd(c,d)=1c, d > 1, \gcd(c, d) = 1q2=cdq _ 2 = \frac cd,此时输出 {c}*sqrt({r})/{d}

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

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

输入格式

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

接下来 TT 行,每行包含三个整数 a,b,ca,b,c

输出格式

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

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

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

输入/输出数据 2

见附件中的 uqe2.inuqe2.ans

数据范围

对于所有数据有:1T50001 \leq T \leq 50001M1031 \leq M \leq 10 ^ 3a,b,cM|a|,|b|,|c| \leq Ma0a \neq 0

测试点编号 MM \leq 特殊性质 A 特殊性质 B 特殊性质 C
11
22 2020
33 10310 ^ 3
44
55
66
7,87, 8
9,109, 10
  • 特殊性质 A:保证 b=0b = 0
  • 特殊性质 B:保证 c=0c = 0
  • 特殊性质 C:如果方程有解,那么方程的两个解都是整数。