众所周知,对一元二次方程 ax2 + bx + c = 0, (a ≠ 0),可以用以下方式求实数解:
计算 Δ=b2 − 4ac,则:
1、若 Δ < 0,则该一元二次方程无实数解。
2、否则 Δ≥0,此时该一元二次方程有两个实数解 x1,2 = (−b±√Δ)/2a。(√为开根号,√Δ即对Δ开根号)
例如:
x2 + x + 1 = 0 无实数解,因为 Δ=12 − 4×1×1 = −3 < 0 。
x2 - 2x + 1 = 0 有两相等实数解 x1,2 = 1。
x2 - 3x + 2 = 0 有两互异实数解 x1 = 1, x2 = 2。
在题面描述中 a 和 b 的最大公因数使用 gcd(a, b) 表示。例如 12 和 18 的最大公因数是 6,即 gcd(12,18)=6。
【题目描述】
现在给定一个一元二次方程的系数 a, b, c,其中 a, b, c 均为整数且 a≠0。
你需要判断一元二次方程 ax2 + bx + c = 0 是否有实数解,并按要求的格式输出。
在本题中输出有理数 v 时须遵循以下规则:
1、由有理数的定义,存在唯一的两个整数 p 和 q,满足 q>0,gcd(p, q) = 1 且 v = p/q。
2、若 q = 1,则输出 {p},否则输出 {p}/{q},其中 {n} 代表整数 n 的值;例如:
-
当 v = −0.5 时,p 和 q 的值分别为 −1 和 2,则应输出 -1/2;
-
当 v = 0 时,p 和 q 的值分别为 0 和 1,则应输出 0。
对于方程的求解,分两种情况讨论:
1、若 Δ = b2 − 4ac < 0,则表明方程无实数解,此时你应当输出 NO;
2、否则 Δ≥0,此时方程有两解(可能相等),记其中较大者为 x,则:
-
(1) 若 x 为有理数,则按有理数的格式输出 x。
-
(2) 否则根据上文公式,x 可以被唯一表示为 x = q1 + q2√r 的形式,其中:
-
q1, q2 为有理数,且 q2 > 0;
-
r 为正整数且 r > 1,且不存在正整数 d > 1 使 d2 | r(即 r* 不应是 d2 的倍数);
-
此时:
-
(1) 若 q1 ≠ 0,则按有理数的格式输出 q1,并再输出一个加号 +;
-
(2) 否则跳过这一步输出;
随后:
-
(1) 若 q2 = 1,则输出 sqrt({r});
-
(2) 否则若 q2 为整数,则输出 {q2}*sqrt({r});
-
(3) 否则若 q3 为整数,则输出 sqrt({r})/{q3};
-
(4) 否则可以证明存在唯一整数 c, d 满足 c, d > 1, gcd(c, d) = 1 且 q2 = c/d,此时输出 {c}*sqrt({r})/{d};
上述表示中 {n} 代表整数 {n} 的值,详见样例。
如果方程有实数解,则按要求的格式输出两个实数解中的较大者。否则若方程没有实数解,则输出 NO。
【输入格式】
输入的第一行包含两个正整数 T, M,分别表示方程数和系数的绝对值上限。
接下来 T 行,每行包含三个整数 a, b, c。
数据范围:1≤T≤5000,1≤M≤1000,|a|,|b|,|c| ≤ M,a ≠ 0
【输出格式】
输出 T 行,每行包含一个字符串,表示对应询问的答案,格式如题面所述。
每行输出的字符串中间不应包含任何空格。
【输入样例】
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
【参考程序】
// 爱码岛编程 P9750
#include <bits/stdc++.h>
using namespace std;
// 求最大公约数 __gcd(p, q) p/q
int gcd(int p, int q) {
int t = 0;
while (q != 0) {
t = p % q;
p = q;
q = t;
}
return p;
}
// p/q
void fun1(int p, int q) {
if (p * q < 0) {
cout << "-";
}
if (p < 0) p = -p;
if (q < 0) q = -q;
int g = gcd(p, q);
if (q == g) {
cout << p / g;
} else {
cout << p / g << "/" << q / g;
}
}
// q/q sqrt
void fun2(int p, int q) {
if (q < 0) q = -q;
int t = 1;
for (int i = sqrt(p); i >= 2; i--) {
if (p % (i * i) == 0) {
p = p / (i * i);
t = t * i;
break;
}
}
int g = gcd(t, q);
t = t / g;
q = q / g;
if (t != 1) {
cout << t << "*";
}
if (p != 1) {
cout << "sqrt(" << p << ")";
}
if (q != 1) {
cout << "/" << q;
}
}
int T, M, a, b, c;
int main() {
cin >> T >> M;
while (T--) {
cin >> a >> b >> c;
int delta = b * b - 4 * a * c;
if (delta < 0) {
cout << "NO";
} else {
int d = sqrt(delta);
if (d * d == delta) {
double x1 = (-b + d) / 2.0 * a;
double x2 = (-b - d) / 2.0 * a;
if (x1 >= x2) {
if (-b + d == 0) {
cout << 0;
} else {
fun1(-b + d, 2 * a);
}
} else {
if (-b - d == 0) {
cout << 0;
} else {
fun1(-b - d, 2 * a);
}
}
} else {
if (b != 0) {
fun1(-b, 2 * a);
cout << "+";
}
fun2(delta, 2 * a);
}
}
cout << endl;
}
return 0;
}