题目描述
众所周知,对一元二次方程 $ax ^ 2 + bx + c = 0, (a \neq 0)$,可以用下述方式求实数解:
- 计算 $\Delta = b ^ 2 - 4ac$,则:
- 若 $\Delta < 0$,则该一元二次方程无实数解;
- 否则 $\Delta \geq 0$,此时该一元二次方程有两个实数解 $x_{1, 2} = \frac{-b \pm \sqrt \Delta}{2a}$;
- 其中,$\sqrt \Delta$ 表示 $\Delta$ 的算数平方根,即使得 $s^2 = \Delta$ 的唯一非负实数 $s$。
- 特别的,当 $\Delta = 0$ 时,这两个实数解相等;当 $\Delta > 0$ 时,这两个实数解互异。
例如:
- $x ^ 2 + x + 1 = 0$ 无实数解,因为 $\Delta = 1 ^ 2 - 4 \times 1 \times 1 = -3 < 0$;
- $x ^ 2 - 2x + 1 = 0$ 有两相等实数解 $x_{1, 2} = 1$;
- $x ^ 2 - 3x + 2 = 0$ 有两互异实数解 $x_1 = 1, x_2 = 2$;
在题面描述中 $a$ 和 $b$ 的最大公因数使用 $\gcd(a, b)$ 表示。
例如 $12$ 和 $18$ 的最大公因数是 $6$,即 $\gcd(12, 18) = 6$。
现在给定一个一元二次方程的系数 $a, b, c$,其中 $a, b, c$ 均为整数且 $a \neq 0$。
你需要判断一元二次方程 $a x ^ 2 + bx + c = 0$ 是否有实数解,并按要求的格式输出。
在本题中输出有理数 $v$ 时须遵循以下规则:
- 由有理数的定义,存在唯一的两个整数 $p$ 和 $q$,满足 $q > 0$,$\gcd(p, q) = 1$ 且 $v = \frac pq$。
- 若 $q = 1$,则输出
{p}
,否则输出 {p}/{q}
,其中 {n}
代表整数 $n$ 的值;
- 例如:
- 当 $v = -0.5$ 时,$p$ 和 $q$ 的值分别为 $-1$ 和 $2$,则应输出
-1/2
;
- 当 $v = 0$ 时,$p$ 和 $q$ 的值分别为 $0$ 和 $1$,则应输出
0
。
对于方程的求解,分两种情况讨论:
- 若 $\Delta = b ^ 2 - 4ac < 0$,则表明方程无实数解,此时你应当输出
NO
;
- 否则 $\Delta \geq 0$,此时方程有两解(可能相等),记其中较大者为 $x$,则:
- 若 $x$ 为有理数,则按有理数的格式输出 $x$。
- 否则根据上文公式,$x$ 可以被唯一表示为 $x = q_1 + q_2 \sqrt r$ 的形式,其中:
- $q_1, q_2$ 为有理数,且 $q_2 > 0$;
- $r$ 为正整数且 $r > 1$,且不存在正整数 $d > 1$ 使 $d ^ 2 \mid r$(即 $r$ 不应是 $d ^ 2$ 的倍数);
此时:
- 若 $q_1 \neq 0$,则按有理数的格式输出 $q_1$,并再输出一个加号
+
;
- 否则跳过这一步输出;
随后:
- 若 $q_2 = 1$,则输出
sqrt({r})
;
- 否则若 $q_2$ 为整数,则输出
{q2}*sqrt({r})
;
- 否则若 $q_3 = \frac{1}{q_2}$ 为整数,则输出
sqrt({r})/{q3}
;
- 否则可以证明存在唯一整数 $c, d$ 满足 $c, d > 1, \gcd(c, d) = 1$ 且 $q _ 2 = \frac cd$,此时输出
{c}*sqrt({r})/{d}
;
上述表示中 {n}
代表整数 $n$ 的值,详见样例。
如果方程有实数解,则按要求的格式输出两个实数解中的较大者。
否则若方程没有实数解,则输出 NO
。
输入格式
输入的第一行包含两个正整数 $T, M$,分别表示方程数和系数的绝对值的上界;
接下来 $T$ 行,每行包含三个整数 $a, b, c$。
输出格式
输出 $T$ 行,每行包含一个字符串,表示对应询问的答案,格式如题面所述。
每行输出的字符串中间不应包含任何空格。
数据范围
对于所有测试数据有:$1 \leq T \leq 5000$,$1 \leq M \leq 10 ^ 3$,$|a|,|b|,|c| \leq M$,$a \neq 0$。

其中:
- 特殊性质 $A$:保证 $b = 0$;
- 特殊性质 $B$:保证 $c = 0$;
- 特殊性质 $C$:如果方程有解,那么方程的两个解都是整数。
输入样例:
9 1000
1 -1 0
1 -2 1
1 5 4
4 4 1
1 0 -432
1 -3 1
2 -4 1
1 7 1
输出样例:
NO
/
*()
/+()/
+()/
/+*()/
算法1
(大模拟) $O(n^2)$
题目写得很恐怖,其实所代表的意思并不难。
也就是考验你的语文水平和耐心。
不好意思,和同学写规则怪谈写多了,注意事项出现了好多类似“你需要”“不需要”“在遵守”的字眼…
我们梳理一下题意:
给出 一元二次方程 $ax ^ 2 + bx + c = 0, (a \neq 0)$,求出在实数范围内较大的 $x$。
然而我们并不需要想如何求解,题目中已经给出了方法。
这里建议先去看懂题目,然后看我们的解题过程,可能会清楚一点。
- 计算 $\Delta = b ^ 2 - 4ac$,则:
- 若 $\Delta < 0$,则该一元二次方程无实数解,此时我们输出
NO
。记得需要回车。
- 否则 $\Delta \geq 0$,此时该一元二次方程有两个实数解 $x_{1, 2} = \frac{-b \pm \sqrt \Delta}{2a}$;而题目中我们只需要求较大的 $x$ 即可。
从上述的第 $2$ 点开始分类讨论:
($1$) $\Delta = 0$
我们把 $x$ 的式子抄下来:$x = \frac{-b \pm \sqrt \Delta}{2a}$。
为了方便描述。
我们
将 $-b \pm \sqrt \Delta$ 记为$p$;
将 $2a$ 记为 $q$。
于是 $x = \frac{p}{q}$。
由于此时 $\Delta = 0$
所以 $\sqrt{\Delta} = 0$,所以 $p = -b + \sqrt{\Delta} = -b + 0 = -b$。
接下来我们将分子分母同时除以 $gcd(p,q)$ 使 $x$ 化为最简分式。(最简公分母即为 $gcd(p,q)$)
同时,我们把分母的负号移到分子上。
由于此时 $\sqrt{\Delta} = 0$ ,所以 $x$ 必为 有理数。
我们直接按分数的输出方法输出 $x$ 即可。
注意: $x$ 可能为整数,此时不要输出 $/q$
($2$) $\Delta \geq 0$
这种情况会比上面的情况复杂得多,请耐心观看。
首先,我们
将 $-b$ 记为$p$;
将 $2a$ 记为 $q$。
将 $ \sqrt \Delta$ 定义为 $sd$
注意:
1. 此时 $p$ 的定义与上文定义有些许不同,表现为没有 $\pm \sqrt \Delta$。
2. $sd$ 中的 $\sqrt \Delta$ 没有 $\pm$,原因后面讲。
3. $sd$ 变量属性为 $long \ long$,原因后面讲。
此时我们的 $x = \frac{p + sd}{2a}$。
以下分两种情况讨论:
① ${sd}^2 = \Delta$,即 $\Delta$ 为 完全平方数。
由于我们的 $sd$ 为 $long \ long$ 属性,存储时会将 $\sqrt \Delta$ 四舍五入。
那我们就可以根据此种特性判断 $\Delta$ 是否为 完全平方数。(此处解释完成注意事项 $3$)
我们将 $q$ 中的负号移到 分子的$p$ 上。
接着 $p + sd$。
$Q:$ 为什么此处 $p$ 不先加上 $sd$ 再进行$\underline{负号转移}$ (指将分母的负号移到分子上) ?
$A:$ 按问题中所说的方法不能保证 $x$ 为较大解。
为了更加清楚地看到问题,我们设 $p = 4$,$q = -2$,$sd = 3$。
问题中的方法: $x = \frac{4 + 3}{-2} = \frac{-7}{2} = - \frac{7}{2}$
正确的方法: $x = \frac{-4 + 3}{-(-2)} = \frac{-1}{2} = - \frac{1}{2}$
显然正确方法中的 $x$ 更大。
注意事项 $2$ 的意义就是为了不要在此过程中加上绝对值符号,会更加麻烦。
接下来约分后输出
注意: $q = 1$ 时不需要输出 $/q$。
② ${sd}^2 \not= \Delta$,即此时 $\Delta$ 不为 完全平方数。
说一句与分类讨论无关的话:你可能觉得 $sd$ 只是用于判断 $\Delta$ 是否为完全平方数,但事实上不是这样的,我们在后面把 $\sqrt{\Delta}$ 化为最简二次根式时也会用到。所以不要把它写在 $if$ 里面。
由于此时 $\Delta$ 不为完全平方数,所以 $\sqrt{\Delta}$ 为无理数,我们需要将其化为最简二次根式再输出,所以此时我们根据题意改变 $x$ 的表示,分批输出。
$$x = \frac{p}{q} + \frac{ \pm \sqrt{\Delta}}{q}$$
首先我们输出 $x$ 中的 $\frac{p}{q}$。
约为最简分式,将 $q$ 中的负号移到 $p$ 上,输出。(此处说过多次,不再赘述)
注意:
- 当 $p = 0$ 时 $\frac{p}{q} = 0$ (显而易见),不需要输出
- 在遵循上述条件 $1$ 的情况下,如果 $q = 1$ ,不需要输出 $/q$
接下来处理后半部分的 $\frac{ \pm \sqrt{\Delta}}{q}$。
我们将 $\sqrt{\Delta}$ 化为最简二次根式(题目中有解释),将其记为 $d1 \sqrt{d2}$。
$Q:$ 如何化简呢?
$A:$ 定义 $d1 = 1$,$d2 = \Delta$。
执行 $for$ 循环,$i$ 从 $sd$ 开始,不断减 $1$,直到 $i = 1$ 为止。(从后往前是为了节约时间)
过程中我们定义 $j = i^2$。
如果 $\Delta$ 能被 $j$ 整除,我们将 $j$ 从根号中开出,将 $d1$ 乘 $i$ ,把 $d2$ 除以 $j$,$break$。
这里怕一些低年级的巨佬没学过二次根式,我们举一个例子:
这里需要知道 $\sqrt{ab} = \sqrt{a} × \sqrt{b}$
此时我们需要化简 $\sqrt{12}$。
根据上述公式我们可以: $\sqrt{12} = \sqrt{4 × 3} = \sqrt{4} × \sqrt{3} = 2 × \sqrt{3} = 2 \sqrt{3}$
然后按照常规方法化简分式,输出。
$Q:$ 为什么 $q$ 赋值时 取了绝对值。(此处见代码 $q = abs(2 * a)$)
$A:$ 与之前 $sd$ 为什么不加 $\pm$ 差不多,是 $x$ 需输出较大值的问题。
我们把后半部分的分式抄下来: $\frac{ \pm \sqrt{\Delta}}{q}$。
- 当 $q$ 为负数时,我们 上方 $ \pm \sqrt{\Delta}$ 取 $- \sqrt{\Delta}$ 时整个分式为正数,显然比负数大
- 当 $q$ 为正数时,我们 上方 $ \pm \sqrt{\Delta}$ 取 $+ \sqrt{\Delta}$ 时整个分式为正数,显然比负数大
这个问题就解决了。
注意:
1. $q = d1$时,$q$ 与 $d1$ 抵消,直接输出 sqrt(d2)
即可;
2. $q = 1$时,不需要输出 $/q$;
3. $d1 = 1$时,不需要输出 $d1$。
完结撒花!
时间复杂度
参考文献
C++ 代码
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <cmath>
using namespace std;
const int N = 1e3 + 10;
long long t,M;
int main(){
scanf("%lld%lld",&t,&M); // 读入,当然 M 在代码中并没有什么用处(
while(t --){ // 多测
long long a,b,c;
scanf("%lld%lld%lld",&a,&b,&c);
long long delta = b * b - 4 * a * c; // 计算 delta
if(delta < 0) printf("NO\n"); // 无解
else if(delta == 0){ // delta = 0 的情况
long long p = -b,q = 2 * a;
long long g = __gcd(abs(p),abs(q));
p /= g;
q /= g;
if(q < 0){
p = -p;
q = -q;
}
if(q == 1) printf("%lld\n",p);
else printf("%lld/%lld\n",p,q);
}
else{ // delta >= 0 的情况
long long p = -b,q = 2 * a;
long long sd = (long long)sqrt(delta);
if(sd * sd == delta){ // delta 为 完全平方数
if(q < 0){
p = -p;
q = -q;
}
p += sd;
long long g = __gcd(abs(p),abs(q));
p /= g;
q /= g;
if(q == 1) printf("%lld\n",p);
else printf("%lld/%lld\n",p,q);
}
else{ // delta 不为 完全平方数
long long g = __gcd(abs(p),abs(q)); // 前一个分式的处理
p /= g;
q /= g;
if(q < 0){
p = -p;
q = -q;
}
if(p != 0){
if(q == 1) printf("%lld+",p);
else printf("%lld/%lld+",p,q);
}
long long d1 = 1,d2 = delta;
q = abs(2 * a); // 后一个分式的处理
for(long long i = sd;i >= 1;i --){
long long j = i * i;
if(d2 % j == 0){
d2 /= j;
d1 *= i;
break;
}
}
int gdq = __gcd(abs(d1),abs(q));
q /= gdq;
d1 /= gdq;
if(q < 0){
q = -q;
d1 = -d1;
}
if(q == d1) printf("sqrt(%lld)\n",d2);
else if(q == 1) printf("%lld*sqrt(%lld)\n",d1,d2);
else if(d1 == 1) printf("sqrt(%lld)/%lld\n",d2,q);
else printf("%lld*sqrt(%lld)/%lld\n",d1,d2,q);
}
}
}
return 0;
}
应该是最为详细的题解了,$AcWing$ 和 $Luogu$ 上都是。
$$(共 355 行)$$