时间限制: 1000 ms 内存限制: 524288 KB
【题目描述】
众所周知，对一元二次方程 𝑎+𝑏𝑥+𝑐=0,(𝑎≠0)，可以用以下方式求实数解：
∙∙ 计算 Δ=−4ac，则:
1. 若 Δ<0，则该一元二次方程无实数解。
2. 否则 Δ≥0，此时该一元二次方程有两个实数解 x1,2=。
例如：
∙+x+1=0 无实数解，因为 Δ=12−4×1×1=−3<0。
∙−2x+1=0 有两相等实数解 x1,2=1。
∙−3x+2=0 有两互异实数解 x1=1,x2=2。
在题面描述中 𝑎 和 𝑏 的最大公因数使用 gcd(𝑎,𝑏) 表示。例如 12 和 18 的最大公因数是 6，即 gcd(12,18)=6。
现在给定一个一元二次方程的系数 𝑎,𝑏,𝑐，其中 𝑎,𝑏,𝑐 均为整数且 𝑎≠0。你需要判断一元二次方程 𝑎+𝑏𝑥+𝑐=0 是否有实数解，并按要求的格式输出。
在本题中输出有理数 𝑣 时须遵循以下规则：
∙∙ 由有理数的定义，存在唯一的两个整数 𝑝 和 𝑞，满足 𝑞>0，gcd(𝑝,𝑞)=1 且 𝑣=𝑝𝑞。
∙∙ 若 𝑞=1，则输出 {p}，否则输出 {p}/{q}，其中 {n} 代表整数 𝑛 的值；
∙∙ 例如：
∙∙ 当 𝑣=−0.5 时，𝑝 和 𝑞 的值分别为 −1 和 2，则应输出 -1/2；
∙∙ 当 𝑣=0 时，𝑝 和 𝑞 的值分别为 0 和 1，则应输出 0。
对于方程的求解，分两种情况讨论：
1. 若 Δ=−4𝑎𝑐<0，则表明方程无实数解，此时你应当输出 NO；
2. 否则 Δ≥0，此时方程有两解（可能相等），记其中较大者为 𝑥，则：
(1). 若 𝑥 为有理数，则按有理数的格式输出 𝑥。
(2). 否则根据上文公式，𝑥 可以被唯一表示为 𝑥=q1+ 的形式，其中：
∙𝑞1,𝑞2 为有理数，且 𝑞2>0；
∙∙𝑟 为正整数且 𝑟>1，且不存在正整数 𝑑>1 使 ∣𝑟（即 𝑟 不应是
的倍数）；
此时：
1. 若 𝑞1≠0，则按有理数的格式输出 𝑞1，并再输出一个加号 +；
2. 否则跳过这一步输出；
随后：
1. 若 𝑞2=1，则输出 sqrt({r})；
2. 否则若 𝑞2 为整数，则输出 {q2}*sqrt({r})；
3. 否则若 𝑞3=1𝑞2 为整数，则输出 sqrt({r})/{q3}；
4. 否则可以证明存在唯一整数 𝑐,𝑑 满足 𝑐,𝑑>1,gcd(𝑐,𝑑)=1 且 𝑞2=𝑐𝑑，此时输出{c}*sqrt({r})/{d}；
上述表示中 {n} 代表整数 {n} 的值，详见样例。
如果方程有实数解，则按要求的格式输出两个实数解中的较大者。否则若方程没有实数解，则输出 NO。
【输入】
输入的第一行包含两个正整数 𝑇,𝑀，分别表示方程数和系数的绝对值上限。
接下来 𝑇 行，每行包含三个整数 𝑎,𝑏,𝑐。
【输出】
输出 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
【提示】
【数据范围】
对于所有数据有：1≤T≤50001≤𝑇≤5000，1≤M≤1031≤𝑀≤103，∣a∣,∣b∣,∣c∣≤M∣𝑎∣,∣𝑏∣,∣𝑐∣≤𝑀，a≠0𝑎≠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：如果方程有解，那么方程的两个解都是整数。
代码样例（要有耐心，有一点麻烦）
（时间总复杂度为 72ms (未任何优化))
#include<bits/stdc++.h>
using namespace std;
int js,f[10005],num[10005];
int gcd(int x,int y)
{if(y==0) return abs(x);//确保最大公因数不为负数 return gcd(y,x%y);
}
void solve(int as)//求sqrt()里面的质因数
{int j=2;while(as>1){if(as%j==0)f[++js]=j;while(as%j==0){num[js]++;as/=j;}j++;}
}
int main()
{ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);int n,m;cin>>n>>m;for(int i=1;i<=n;i++){int a,b,c;js=0;cin>>a>>b>>c;if(a<0)//确保a为正数 {a=-a;b=-b;c=-c;}int h=b*b-4*a*c;//sqrt()里面的值 if(h<0)//如果sqrt()里面小于0，即无解 {cout<<"NO"<<'\n';continue;//下次判断 }int sq=sqrt(h);if(sq*sq==h)//如果h可以直接开平方 {int yy=-b+sq;//求-b+sqrt(h) int xx=gcd(yy,2*a);//求最大公因数 yy=yy/xx;//化为最简 int y=2*a/xx;//化为最简 if(y==1)cout<<yy/y<<'\n';//防止出现想（2/1）这种情况 elsecout<<yy<<"/"<<y<<'\n';//输出 continue; //下次判断 }if(b>0)//说明-b是负数，但为了判断最大公因数，将b取绝对值 cout<<"-";b=abs(b);//确保b为正数 if(b!=0)//只有b有值，才有前面的部分 {int g=gcd(b,2*a);//求最大公因数 b=b/g;//化为最简 int hh=2*a/g;//化为最简 if(hh==1)//即不需要输出1 cout<<b/hh;elsecout<<b<<'/'<<hh;//输出分数 if(h==0)//即不存在后面的部分 {cout<<'\n';continue;//下次判断 }cout<<'+';//准备输出后面的部分 }memset(num,0,sizeof(num));solve(h);//求质因数 int df=1,fd=1;//df为sqrt()外面的数，fd为sqrt()里面的数 for(int i=1;i<=js;i++){if(num[i]>1)//即可以将f[i]取出来 {df*=pow(f[i],num[i]/2);//df乘以f[i] if(num[i]%2==1)//如果num[i]为奇数，即在sqrt()会留下一个f[i] fd*=f[i];//乘以f[i] }elsefd*=f[i];//乘以f[i] }int g1=gcd(df,2*a);//算最大公因数 df=df/g1;//化为最简 int hh1=2*a/g1;//化为最简 if(df!=1)//如果为1，则不需要输出 cout<<df<<'*';cout<<"sqrt(";cout<<fd<<')';//输出fd if(hh1!=1)//如果为1，（分母为1，不需要输出） cout<<'/'<<hh1;cout<<'\n';}return 0;
} 
