[CSP-J2023]一元二次方程题解
2026-08-08 10:03:04
发布于：广东
[CSP-J 2023] 一元二次方程 题解
一、先理解题目（不要急着抽象）
【简单理解】
这道题其实是在解决：
给你很多个一元二次方程：
ax^2 + bx + c = 0
其中 a、b、c 都是整数，并且 a != 0。
我们要做两件事：
- 判断这个方程有没有实数解；
- 如果有实数解，输出两个解里面较大的那个，并且必须按照题目规定的格式输出。
题目里面的东西可以这样理解：
a、b、c：方程的三个系数；x：未知数；T：一共有多少个方程要处理；M：系数绝对值的上限，主要告诉我们数据不会太大；- 最后要输出的答案：较大的那个实数根，或者
NO。
例如：
x^2 - 3x + 2 = 0
它的两个解是 1 和 2，较大的是 2，所以输出 2。
再例如：
x^2 + x + 1 = 0
它没有实数解，所以输出 NO。
注意：这道题难点不在于“会不会公式”，而在于“能不能把答案整理成题目要求的样子”。
二、题意抽象（从故事变成数学问题）
【抽象之后】
给定：
a, b, c
要求：
求方程
ax^2 + bx + c = 0
的较大实数解。
本质：
- 用判别式判断有没有实数解；
- 如果有解，用求根公式得到较大的解；
- 把答案化简后按格式输出。
我们真正需要处理的关键信息是：
delta = b^2 - 4ac
也就是题目中常说的判别式。
背景里关于数学公式的描述不需要害怕，我们只要把它拆成几个固定步骤即可。
题目要求的输出格式整理（非常关键）
这道题在写代码前，一定要先把输出格式整理清楚。
不然很容易出现这种情况：
公式会算，但是不知道什么时候输出 sqrt(...)，什么时候输出 /q，什么时候要加 +。
我们把题目要求分成下面几类。
1. 没有实数解
如果：
delta < 0
直接输出：
NO
这一类最简单，后面不用再处理。
2. 答案是有理数
有理数可以理解成“能写成分数的数”。
题目要求所有有理数都要化成最简形式：
p/q
并且必须满足：
q > 0，分母必须是正数；gcd(p, q) = 1，也就是分子分母不能再约分；- 如果
q = 1，只输出p； - 如果
q != 1，输出p/q。
例如：
4/2
要输出：
2
例如：
-6/8
要输出：
-3/4
在本题中，什么时候答案是有理数？
当 delta 是完全平方数时，sqrt(delta) 是整数。
这时较大根：
(-b + sqrt(delta)) / (2a)
就是一个普通分数，直接约分输出。
3. 答案是无理数
如果 delta 不是完全平方数，答案会带根号。
题目要求把答案整理成：
q1 + q2 * sqrt(r)
其中：
q1是有理数；q2是正有理数；r是根号里面剩下的整数；r > 1；r不能再被平方数整除，也就是根号必须化简到最简。
比如：
sqrt(12)
不能直接输出 sqrt(12)，因为：
sqrt(12) = 2*sqrt(3)
所以 r 应该是 3。
4. 无理数的输出顺序
先看有理数部分 q1。
如果：
q1 != 0
先按有理数格式输出 q1，再输出一个加号：
q1+
如果：
q1 = 0
这一部分直接跳过，不能输出：
0+
然后输出根号部分 q2*sqrt(r)。
根号部分也要分情况：
q2 的情况 |
输出格式 |
|---|---|
q2 = 1 |
sqrt(r) |
q2 是大于 1 的整数 |
q2*sqrt(r) |
q2 = 1/q3 |
sqrt(r)/q3 |
q2 = c/d，且 c > 1, d > 1 |
c*sqrt(r)/d |
举几个例子：
1 + sqrt(3)
输出：
1+sqrt(3)
1 + 2*sqrt(3)
输出：
1+2*sqrt(3)
1 + sqrt(3)/2
输出：
1+sqrt(3)/2
1 + 2*sqrt(3)/3
输出：
1+2*sqrt(3)/3
三、思考如何解决（先讲思考过程）
1. 最直接的方法是什么？
最直接的想法是：
- 用
double算出两个根； - 比较哪个更大；
- 直接输出小数。
这种方法不行。
原因是题目不让我们输出小数，而是要求输出精确形式。
例如：
(3 + sqrt(5)) / 2
不能写成：
2.6180339887
因为小数会有误差，而且格式也不符合题目要求。
2. 观察题目特点
这道题有几个很重要的特点：
- 系数都是整数；
M <= 1000，所以判别式不会特别大；- 答案可能是有理数，也可能带有
sqrt(...)； - 输出格式要求非常严格，不能多空格，不能漏约分。
这说明我们不应该用浮点数，而应该一直用整数来处理。
3. 得出算法选择
因为题目主要是在模拟数学化简过程，所以这道题可以看成一道“数学模拟题”。
这里的“模拟”意思是：
按照题目要求，一步一步判断、化简、输出，而不是套一个复杂算法。
我们要做的是：
- 计算
delta = b * b - 4 * a * c； - 如果
delta < 0，输出NO； - 否则，较大根来自公式：
(-b + sqrt(delta)) / (2a)
- 把它整理成题目要求的形式。
还有一个细节：
如果 a < 0，那么分母 2a 是负的。为了让分母保持正数，我们可以把 a、b、c 同时变成相反数。
这是合法的，因为：
ax^2 + bx + c = 0
两边同时乘以 -1，方程的解不会改变。
四、算法核心思想（重点讲理解）
1. 判断有没有实数解
先计算：
delta = b^2 - 4ac
如果：
delta < 0
那么根号里面是负数，没有实数解，输出：
NO
如果：
delta >= 0
那么有实数解。
2. 为什么较大根用加号？
当我们已经把 a 处理成正数时，分母 2a 是正数。
两个根是：
(-b - sqrt(delta)) / (2a)
(-b + sqrt(delta)) / (2a)
因为 sqrt(delta) >= 0，所以加上根号的那个分子更大。
分母又是正数，所以较大的根就是：
(-b + sqrt(delta)) / (2a)
3. 如果答案是有理数
当 delta 是完全平方数时，sqrt(delta) 是整数。
例如：
delta = 9
sqrt(delta) = 3
此时较大根就是：
(-b + 3) / (2a)
这是一个分数，直接约分输出即可。
例如：
4 / 2
要输出：
2
不能输出：
4/2
4. 如果答案带根号
如果 delta 不是完全平方数，就要把根号化简。
例如：
sqrt(12)
可以变成：
2*sqrt(3)
因为：
12 = 4 * 3
sqrt(12) = sqrt(4 * 3) = 2 * sqrt(3)
所以我们要找到最大的平方数因子。
假设：
sqrt(delta) = out * sqrt(in)
那么较大根可以写成：
(-b) / (2a) + out * sqrt(in) / (2a)
然后分别化简：
- 有理数部分：
(-b) / (2a)； - 根号部分：
out / (2a)作为sqrt(in)前面的系数。
五、用简单例子模拟算法过程
我们用这个方程：
x^2 - 3x + 1 = 0
也就是：
a = 1, b = -3, c = 1
第一步，计算判别式：
delta = b^2 - 4ac
= (-3)^2 - 4 * 1 * 1
= 9 - 4
= 5
delta = 5，不是负数，所以有实数解。
第二步，确定较大根：
(-b + sqrt(delta)) / (2a)
代入：
(3 + sqrt(5)) / 2
第三步，拆成两部分：
3/2 + sqrt(5)/2
所以输出：
3/2+sqrt(5)/2
注意中间不能有空格。
再看一个能化简根号的例子：
x^2 - 2x - 2 = 0
a = 1, b = -2, c = -2
delta = (-2)^2 - 4 * 1 * (-2)
= 4 + 8
= 12
sqrt(12) = 2*sqrt(3)
较大根：
(2 + 2*sqrt(3)) / 2
两部分都除以 2：
1 + sqrt(3)
输出：
1+sqrt(3)
六、复杂度分析
对于每个方程，我们要做的事情主要有：
- 计算判别式，常数时间；
- 求最大公因数，次数很少；
- 枚举可能的平方因子。
因为 M <= 1000，所以 delta 最大大约是几百万级别，sqrt(delta) 只有几千。
因此每个方程最多枚举几千次。
时间复杂度可以写成：
O(T * sqrt(delta))
在本题数据范围下可以通过。
空间复杂度：
O(1)
因为我们只用了几个变量，没有开很大的数组。
七、代码实现思路
代码需要这些变量：
_：方程数量；M：系数范围，读入后不用特别处理；a, b, c：方程系数；d：判别式；q：分母，也就是2 * a；out：根号外面的系数；in：根号里面剩下的数。
还需要两个辅助函数：
gcdll：求最大公因数；frac：把一个分数化简成题目要求的字符串。
#include<bits/stdc++.h>
#define int long long
using namespace std;
int M;
int gcdll(int a,int b){
a=abs(a),b=abs(b);
return b?gcdll(b,a%b):a;
}
string frac(int p,int q){
if(q<0) p=-p,q=-q;
int g=gcdll(p,q);
p/=g,q/=g;
if(q==1) return to_string(p);
return to_string(p)+"/"+to_string(q);
}
int sqr(int x){
int t=sqrt((long double)x);
while((t+1)*(t+1)<=x) t++;
while(t*t>x) t--;
return t;
}
bool ok(int x){
int t=sqr(x);
return t*t==x;
}
void solve(){
int a,b,c;
cin>>a>>b>>c;
if(a<0) a=-a,b=-b,c=-c;
int d=b*b-4*a*c;
if(d<0){
cout<<"NO\n";
return;
}
int q=2*a;
if(ok(d)){
cout<<frac(-b+sqr(d),q)<<'\n';
return;
}
int out=1,in=d;
for(int i=sqr(d);i>=1;i--){
if(d%(i*i)==0){
out=i;
in=d/(i*i);
break;
}
}
string ans="";
if(-b!=0) ans+=frac(-b,q)+"+";
int g=gcdll(out,q);
out/=g,q/=g;
if(out!=1) ans+=to_string(out)+"*";
ans+="sqrt("+to_string(in)+")";
if(q!=1) ans+="/"+to_string(q);
cout<<ans<<'\n';
}
signed main(){
std::ios::sync_with_stdio(false);
cout.tie(0);cin.tie(0);
int _=1;
cin>>_>>M;
while(_--){
solve();
}
return 0;
}
八、代码逐步解释
1. 为什么要写 frac
题目中多次需要输出分数。
例如：
-b / (2a)
out / (2a)
如果每次都手写约分逻辑，代码容易乱，也容易漏细节。
所以我们写一个函数专门处理分数：
- 保证分母是正数；
- 用最大公因数约分；
- 如果分母是
1，只输出整数； - 否则输出
p/q。
2. 为什么 a < 0 时要整体变号
较大根公式里有分母 2a。
如果 a 是负数，比较两个根时加号和减号的大小关系会反过来。
为了让后面统一处理，我们把方程整体乘以 -1，让 a 变成正数。
这样分母一定是正数，较大根就固定是：
(-b + sqrt(delta)) / (2a)
3. 为什么要找最大的平方因子
根号要化简到最简。
例如：
sqrt(72)
如果只写：
sqrt(72)
不符合最简要求。
因为：
72 = 36 * 2
sqrt(72) = 6*sqrt(2)
所以我们从 sqrt(delta) 往下找，找到最大的 i，使得：
i * i 能整除 delta
这个 i 就是根号外面的系数。
九、易错点总结
- 忘记处理
delta < 0
根号里面是负数时没有实数解，应该直接输出 NO。
- 用
double输出答案
题目要求精确格式，不能输出小数。
a < 0时没有统一分母符号
如果分母是负数，较大根的判断和分数格式都会变麻烦。推荐先把 a、b、c 同时取相反数。
- 分数没有约分
例如 4/2 应该输出 2，不是 4/2。
- 根号没有化简
例如 sqrt(12) 应该输出 2*sqrt(3)。
- 多输出了
1*
应该输出：
sqrt(5)
不要输出：
1*sqrt(5)
- 多输出了
/1
应该输出：
sqrt(5)
不要输出：
sqrt(5)/1
- 有理数部分是
0时还输出0+
应该输出：
sqrt(5)
不要输出：
0+sqrt(5)
十、最后总结解题方法
这道题考察的是：
- 一元二次方程求根公式；
- 判别式判断实数解；
- 分数约分；
- 二次根式化简；
- 严格按格式输出。
看到这类题：
第一步：
先判断有没有解，也就是看 delta 是否小于 0。
第二步：
确定较大根来自哪个公式。为了方便处理，可以先保证 a > 0。
第三步：
判断 delta 是否是完全平方数。
第四步：
如果是有理数，按分数规则输出；如果带根号，先化简根号，再拆成“有理数部分 + 根号部分”输出。
核心习惯：
不要急着写代码，先把答案可能出现的格式分清楚，再逐类处理。
这里空空如也
有帮助，赞一个