洛谷 P9750
众所周知，对一元二次方程 ax2+bx+c=0,(a=0)，可以用以下方式求实数解：
- 计算 Δ=b2−4ac，则:
- 若 Δ<0，则该一元二次方程无实数解。 2. 否则 Δ≥0，此时该一元二次方程有两个实数解 x1,2=2a−b±Δ。
例如：
- 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 时须遵循以下规则：
- 由有理数的定义，存在唯一的两个整数 p 和 q，满足 q>0，gcd(p,q)=1 且 v=qp。
- 若 q=1，则输出
{p}，否则输出 {p}/{q}，其中 {n} 代表整数 n 的值；
- 例如：
- 当 v=−0.5 时，p 和 q 的值分别为 −1 和 2，则应输出
-1/2；
- 当 v=0 时，p 和 q 的值分别为 0 和 1，则应输出
0。
对于方程的求解，分两种情况讨论：
-
若 Δ=b2−4ac<0，则表明方程无实数解，此时你应当输出 NO；
-
否则 Δ≥0，此时方程有两解（可能相等），记其中较大者为 x，则：
-
若 x 为有理数，则按有理数的格式输出 x。
-
否则根据上文公式，x 可以被唯一表示为 x=q1+q2r 的形式，其中：
- $q _ 1, q _ 2$ 为有理数，且 $q _ 2 > 0$；
- r 为正整数且 r>1，且不存在正整数 d>1 使 d2∣r（即 r 不应是 d2 的倍数）；
此时：
- 若 q1=0，则按有理数的格式输出 q1，并再输出一个加号
+；
- 否则跳过这一步输出；
随后：
- 若 q2=1，则输出
sqrt({r})；
- 否则若 q2 为整数，则输出
{q2}*sqrt({r})；
- 否则若 q3=q21 为整数，则输出
sqrt({r})/{q3}；
- 否则可以证明存在唯一整数 c,d 满足 c,d>1,gcd(c,d)=1 且 q2=dc，此时输出
{c}*sqrt({r})/{d}；
上述表示中 {n} 代表整数 {n} 的值，详见样例。
如果方程有实数解，则按要求的格式输出两个实数解中的较大者。否则若方程没有实数解，则输出 NO。
输入格式
输入的第一行包含两个正整数 T,M，分别表示方程数和系数的绝对值上限。
接下来 T 行，每行包含三个整数 a,b,c。
输出格式
输出 T 行，每行包含一个字符串，表示对应询问的答案，格式如题面所述。
每行输出的字符串中间不应包含任何空格。
输入输出样例 #1
输入 #1
1
2
3
4
5
6
7
8
9
10
| 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
1
2
3
4
5
6
7
8
9
| 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】
见附件中的 uqe/uqe2.in 与 uqe/uqe2.ans。
【数据范围】
对于所有数据有：1≤T≤5000，1≤M≤103，∣a∣,∣b∣,∣c∣≤M，a=0。
| 测试点编号 | M≤ | 特殊性质 A | 特殊性质 B | 特殊性质 C |
| :------## --: | :—## : | :—## --: | :—## --: | :-----: |
| 1 | 1 | 是 | 是 | 是 |
| 2 | 20 | 否 | 否 | 否 |
| 3 | 103 | 是 | 否 | 是 |
| 4 | 103 | 是 | 否 | 否 |
| 5 | 103 | 否 | 是 | 是 |
| 6 | 103 | 否 | 是 | 否 |
| 7,8 | 103 | 否 | 否 | 是 |
| 9,10 | 103 | 否 | 否 | 否 |
其中：
- 特殊性质 A：保证 b=0；
- 特殊性质 B：保证 c=0；
- 特殊性质 C：如果方程有解，那么方程的两个解都是整数。
题解
这题相当的麻烦啊，要考虑很多边缘情况，比如若求得结果为
x=ba+ecd
要考虑 a=0、b=1、c=0、c=1、d=1、e=1 等等，都要做特判
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
| #include <bits/stdc++.h>
using namespace std;
const int gcd(int a, int b){
a = abs(a);
b = abs(b);
return b?gcd(b, a%b):a;
}
const pair<const int, const int> decimalSqrt(int x){
if(!x) return {0, 1};
int i = 2, a = x>0?1:-1, b = 1;
map<int, int> Map;
if(x<0) x = -x;
while(x!=1){
while(!(x%i)){
x /= i;
Map[i]++;
}
i++;
}
for(auto& j : Map){
a *= pow(j.first, j.second/2);
if(j.second&1) b *= j.first;
}
return {a, b};
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int t, m;
cin >> t >> m;
while(t--){
int a, b, c;
cin >> a >> b >> c;
int delta = b*b - 4*a*c;
if(delta<0){
cout << "NO" << endl;
continue;
}
b = -b;
const auto& sd = decimalSqrt(delta);
if(sd.second == 1){
b += a<0?-sd.first:sd.first;
}
if(b){
if(b%(2*a)){
int g = gcd(b, 2*a);
cout << (((b<0)^(a<0))?"-":"") << abs(b/g) << "/" << abs(2*a/g);
}else cout << b/(2*a);
}
if(sd.second!=1){
if(b) cout << "+";
int h = gcd(sd.first, 2*a);
int i = abs(sd.first/h);
if(i!=1) cout << i << "*";
cout << "sqrt(" << sd.second << ")";
if(sd.first%(2*a)) cout << "/" << abs(2*a/h);
}
if(!b && sd.second==1) cout << 0;
cout << endl;
}
return 0;
}
|