題目

題目背景

眾所周知，對一元二次方程 $a{x}^2+bx+c=0,(a\ne 0)$，可以用以下方式求實數解：

• 計算 $\Delta =b^2?4ac$，則:
  1. 若 $\Delta <0$，則該一元二次方程無實數解。
  2. 否則 $\Delta \ge 0$，此時該一元二次方程有兩個實數解 $x_{1,2}=\frac{?b\pm \sqrt{\Delta }}{2a}$。

例如：

• $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\ne 0$。你需要判斷一元二次方程 $a{x}^2+bx+c=0$ 是否有實數解，并按要求的格式輸出。

在本題中輸出有理數 $v$ 時須遵循以下規則：

• 由有理數的定義，存在唯一的兩個整數 $p$ 和 $q$，滿足 $q>0$，$\gcd (p,q)=1$ 且 $v=\frac{p}{q}$。

• 若 $q=1$，則輸出 {p}，否則輸出 {p}/{q}，其中 {n} 代表整數 $n$ 的值；

• 例如：

  • 當 $v=?0.5$ 時，$p$ 和 $q$ 的值分別為 $?1$ 和 $2$，則應輸出 -1/2；
  • 當 $v=0$ 時，$p$ 和 $q$ 的值分別為 $0$ 和 $1$，則應輸出 0。

對于方程的求解，分兩種情況討論：

1. 若 $\Delta =b^2?4ac<0$，則表明方程無實數解，此時你應當輸出 NO；

2. 否則 $\Delta \ge 0$，此時方程有兩解（可能相等），記其中較大者為 $x$，則：

   1. 若 $x$ 為有理數，則按有理數的格式輸出 $x$。

   2. 否則根據上文公式，$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$ 的倍數）；

   此時：

   1. 若 $q_1\ne 0$，則按有理數的格式輸出 $q_1$，并再輸出一個加號 +；
   2. 否則跳過這一步輸出；

   隨后：

   1. 若 $q_2=1$，則輸出 sqrt({r})；
   2. 否則若 $q_2$ 為整數，則輸出 {q2}*sqrt({r})；
   3. 否則若 $q_3=\frac{1}{q_2}$ 為整數，則輸出 sqrt({r})/{q3}；
   4. 否則可以證明存在唯一整數 $c,d$ 滿足 $c,d>1,\gcd (c,d)=1$ 且 $q_2=\frac{c}{d}$，此時輸出 {c}*sqrt({r})/{d}；

   上述表示中 {n} 代表整數 {n} 的值，詳見樣例。

   如果方程有實數解，則按要求的格式輸出兩個實數解中的較大者。否則若方程沒有實數解，則輸出 NO。

輸入格式

輸入的第一行包含兩個正整數 $T,M$，分別表示方程數和系數的絕對值上限。

接下來 $T$ 行，每行包含三個整數 $a,b,c$。

輸出格式

輸出 $T$ 行，每行包含一個字符串，表示對應詢問的答案，格式如題面所述。

每行輸出的字符串中間不應包含任何空格。

樣例 #1

樣例輸入 #1

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
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\le T\le 5000$，$1\le M\le 10^3$，$|a|,|b|,|c|\le M$，$a\ne 0$。

測試點編號	$M\le$	特殊性質 A	特殊性質 B	特殊性質 C
$1$	$1$	是	是	是
$2$	$20$	否	否	否
$3$	$10^3$	是	否	是
$4$	$10^3$	是	否	否
$5$	$10^3$	否	是	是
$6$	$10^3$	否	是	否
$7,8$	$10^3$	否	否	是
$9,10$	$10^3$	否	否	否

其中：

• 特殊性質 A：保證 $b=0$；
• 特殊性質 B：保證 $c=0$；
• 特殊性質 C：如果方程有解，那么方程的兩個解都是整數。

題目傳送門

洛谷 P9750 [CSP-J 2023] 一元二次方程

題解

思路

沒有任何算法，純粹的大模擬，細節還蠻多的

由于這道題有多測，所以用一個函數比較好，可以把 $a,b,c$ 都傳進去，這就是主函數

int T, m;
int a, b, c;
int main() {scanf("%d%d", &T, &m);while(T-- && scanf("%d%d%d", &a, &b, &c))work(a, b, c);return 0;
}

函數里面首先是判斷無解，也就是 $\Delta <0$，那我們就需要算出 $\Delta$，即 $b^2?4ac$

int delta = b * b - 4 * a * c;void work(int a, int b, int c) {delta = b * b - 4 * a * c;if(delta < 0) {puts("NO");return;}
}

然后需要判斷 $\Delta$ 是完全平方數，那么就可以直接算出 $\frac{?b+\sqrt{\Delta }}{2a}$ 和 $\frac{?b?\sqrt{\Delta }}{2a}$ 哪個大，然后如果能除開就直接輸出那個根，否則就輸出約分后的那個根

（那個 $printdivision(p,q)$ 函數是用來輸出 $p/q$ 的，具體請參考注釋）

int delta;
double x1, x2;
int sq;void print_division(int p, int q) {if(!p) {											// 分子為 0，則輸出 0 putchar('0');return;}if(p * q < 0)										// 兩數異號，則輸出符號 putchar('-');if(p < 0)											// 將兩數都變成正數 p = -p;if(q < 0)q = -q;int g = __gcd(p, q);								// 約分 p /= g;q /= g;if(q == 1)											// 分母為 1，則輸出分子 printf("%d", p);else												// 否則輸出 “分子/分母” printf("%d/%d", p, q);
}void work(int a, int b, int c) {delta = b * b - 4 * a * c;if(delta < 0) {puts("NO");return;}sq = sqrt(delta);if(sq * sq == delta) {x1 = 1.0 * (-b + sq) / 2 * a;x2 = 1.0 * (-b - sq) / 2 * a;if(x1 > x2)print_division(-b + sq, 2 * a);elseprint_division(-b - sq, 2 * a);puts("");return;}
}

否則的話就需要按照 “$?b/2a+\sqrt{\Delta }/2a$” 的格式輸出

首先如果 $b\ne 0$，那么就說明 $?b/2a\ne 0$，就可以輸出 “$?b/2a+$”

為什么一定是 $+$ ？因為如果是 $\frac{?b?\sqrt{\Delta }}{2a}$ 更大，那就說明 $2a<0$，否則不可能 $\frac{?b?\sqrt{\Delta }}{2a}>\frac{?b?\sqrt{\Delta }}{2a}$，所以一定是 $+$

最后就是輸出 $\sqrt{\Delta }/2a$ 了，具體怎么做請參考代碼注釋

int delta;
double x1, x2;
int sq;void print_division(int p, int q) {if(!p) {											// 分子為 0，則輸出 0 putchar('0');return;}if(p * q < 0)										// 兩數異號，則輸出符號 putchar('-');if(p < 0)											// 將兩數都變成正數 p = -p;if(q < 0)q = -q;int g = __gcd(p, q);								// 約分 p /= g;q /= g;if(q == 1)											// 分母為 1，則輸出分子 printf("%d", p);else												// 否則輸出 “分子/分母” printf("%d/%d", p, q);
}void print_sqrt(int p, int q) {if(q < 0)											// 如果分母是負數，則將其變為正數，因為和前面的負號消沒了（上文說過了） q = -q;int u = 1;											// 根號前面的系數 for(int i = sqrt(p); i > 1; --i)					// 化簡 if(!(p % (i * i))) {p /= i * i;u *= i;break; }int g = __gcd(u, q);								// 約分 u /= g;q /= g;if(u > 1)											// 系數大于 1，則輸出 “系數*” printf("%d*", u);if(p > 1)											// 根號下的數大于 1，則輸出 “sqrt(根號下的數)” printf("sqrt(%d)", p);if(q > 1)											// 分母大于 1，則輸出 “/分母” printf("/%d", q);
}void work(int a, int b, int c) {delta = b * b - 4 * a * c;if(delta < 0) {puts("NO");return;}sq = sqrt(delta);if(sq * sq == delta) {x1 = 1.0 * (-b + sq) / 2 * a;x2 = 1.0 * (-b - sq) / 2 * a;if(x1 > x2)print_division(-b + sq, 2 * a);elseprint_division(-b - sq, 2 * a);puts("");return;}if(b) {print_division(-b, 2 * a);putchar('+');}print_sqrt(delta, 2 * a);puts("");
}

總代碼

#include <cstdio>
#include <algorithm>
#include <cmath>
using namespace std;int T, m;
int a, b, c;
int delta;
double x1, x2;
int sq;void print_division(int p, int q) {if(!p) {putchar('0');return;}if(p * q < 0)putchar('-');if(p < 0)p = -p;if(q < 0)q = -q;int g = __gcd(p, q);p /= g;q /= g;if(q == 1)printf("%d", p);elseprintf("%d/%d", p, q);
}void print_sqrt(int p, int q) {if(q < 0)q = -q;int u = 1;for(int i = sqrt(p); i > 1; --i)if(!(p % (i * i))) {p /= i * i;u *= i;break; }int g = __gcd(u, q);u /= g;q /= g;if(u > 1)printf("%d*", u);if(p > 1)printf("sqrt(%d)", p);if(q > 1)printf("/%d", q);
}void work(int a, int b, int c) {delta = b * b - 4 * a * c;if(delta < 0) {puts("NO");return;}sq = sqrt(delta);if(sq * sq == delta) {x1 = 1.0 * (-b + sq) / 2 * a;x2 = 1.0 * (-b - sq) / 2 * a;if(x1 > x2)print_division(-b + sq, 2 * a);elseprint_division(-b - sq, 2 * a);puts("");return;}if(b) {print_division(-b, 2 * a);putchar('+');}print_sqrt(delta, 2 * a);puts("");
}int main() {scanf("%d%d", &T, &m);while(T-- && scanf("%d%d%d", &a, &b, &c))work(a, b, c);return 0;
}

提交結果

戳這里看我的提交記錄

尾聲

如果這篇題解對您（或您的團隊）有幫助的話，就幫忙點個贊，加個關注！

最后，祝您_{（或您的團隊）}在 OI 的路上一路順風！！！

┬┴┬┴┤?ω?)ノ Bye~