P9750 [CSP-J 2023] Quadratic Equation

As everyone knows, for the quadratic equation in one variable $ax ^ 2 + bx + c = 0(a \neq 0)$, you can find its real solutions in the following way: - Compute $\Delta = b ^ 2 - 4ac$, then: 1. If $\Delta < 0$, the quadratic equation has no real solution. 2. Otherwise, if $\Delta \geq 0$, the quadratic equation has two real solutions $x _ {1, 2} = \frac{-b \pm \sqrt \Delta}{2a}$. For example: - $x ^ 2 + x + 1 = 0$ has no real solution, because $\Delta = 1 ^ 2 - 4 \times 1 \times 1 = -3 < 0$. - $x ^ 2 - 2x + 1 = 0$ has two equal real solutions $x _ {1, 2} = 1$. - $x ^ 2 - 3x + 2 = 0$ has two distinct real solutions $x _ 1 = 1, x _ 2 = 2$. In this statement, the greatest common divisor of $a$ and $b$ is denoted by $\gcd(a, b)$. For example, the greatest common divisor of $12$ and $18$ is $6$, that is, $\gcd(12, 18) = 6$.

Now you are given the coefficients $a, b, c$ of a quadratic equation in one variable, where **$a, b, c$ are all integers and $a \neq 0$**. You need to determine whether the quadratic equation $a x ^ 2 + bx + c = 0$ has real solutions, and output in the required format. **In this problem, when outputting a rational number $v$, you must follow these rules:** - By the definition of a rational number, there exist unique integers $p$ and $q$ such that $q > 0$, $\gcd(p, q) = 1$, and $v = \frac pq$. - If $q = 1$, **output `{p}`; otherwise output `{p}/{q}`**, where `{n}` denotes the integer value $n$. - For example: - When $v = -0.5$, the values of $p$ and $q$ are $-1$ and $2$, so you should output `-1/2`. - When $v = 0$, the values of $p$ and $q$ are $0$ and $1$, so you should output `0`. **For solving the equation, discuss two cases:** 1. If $\Delta = b ^ 2 - 4ac < 0$, then the equation has no real solution, and you should output `NO`. 2. Otherwise, $\Delta \geq 0$. The equation has two solutions (possibly equal). Let the larger one be $x$, then: 1. If $x$ is a rational number, output $x$ in the rational format. 2. Otherwise, according to the formula above, $x$ can be **uniquely** written in the form $x = q _ 1 + q _ 2 \sqrt r$, where: - $q _ 1, q _ 2$ are rational numbers, and $q _ 2 > 0$. - $r$ is a positive integer and $r > 1$, and there is no positive integer $d > 1$ such that $d ^ 2 \mid r$ (that is, $r$ should not be a multiple of $d ^ 2$). In this case: 1. If $q _ 1 \neq 0$, output $q _ 1$ in the rational format, and then output a plus sign `+`. 2. Otherwise, skip this step. Then: 1. If $q _ 2 = 1$, output `sqrt({r})`. 2. Otherwise, if $q _ 2$ is an integer, output `{q2}*sqrt({r})`. 3. Otherwise, if $q _ 3 = \frac 1{q _ 2}$ is an integer, output `sqrt({r})/{q3}`. 4. Otherwise, it can be proven that there exist unique integers $c, d$ such that $c, d > 1$, $\gcd(c, d) = 1$, and $q _ 2 = \frac cd$. Output `{c}*sqrt({r})/{d}`. In the representations above, `{n}` denotes the integer value `{n}`. See the samples for details. If the equation has real solutions, output the larger one of the two real solutions in the required format. Otherwise, if the equation has no real solution, output `NO`.

The first line contains two positive integers $T, M$, representing the number of equations and the upper bound of the absolute values of the coefficients. The next $T$ lines each contain three integers $a, b, c$.

Output $T$ lines. Each line contains one string representing the answer to the corresponding query, in the format described above. **There should be no spaces in the output string of each line.**

**[Sample #2]** See `uqe/uqe2.in` and `uqe/uqe2.ans` in the attached files. **[Constraints]** For all data: $1 \leq T \leq 5000$, $1 \leq M \leq 10 ^ 3$, $|a|,|b|,|c| \leq M$, and $a \neq 0$. | Test Point ID | $M \leq$ | Special Property A | Special Property B | Special Property C | | :-: | :-: | :-: | :-:| :-:| | $1$ | $1$ | Yes | Yes | Yes | | $2$ | $20$ | No | No | No | | $3$ | $10 ^ 3$ | Yes | No | Yes | | $4$ | $10 ^ 3$ | Yes | No | No | | $5$ | $10 ^ 3$ | No | Yes | Yes | | $6$ | $10 ^ 3$ | No | Yes | No | | $7, 8$ | $10 ^ 3$ | No | No | Yes | | $9, 10$ | $10 ^ 3$ | No | No | No | Where: - Special Property A: guarantees $b = 0$. - Special Property B: guarantees $c = 0$. - Special Property C: if the equation has solutions, then both solutions are integers. Translated by ChatGPT 5