信息学奥赛一本通 2100：【23CSPJ普及组】一元二次方程(uqe) | 洛谷 P9750 [CSP-J 2023] 一元二次方程

【题目链接】

洛谷 P9750 [CSP-J 2023] 一元二次方程
ybt 2100：【23CSPJ普及组】一元二次方程(uqe)

【题目考点】

1. 大模拟

2. 数学：一元二次方程求根

【解题思路】

对一元二次方程求根的过程，并按照题目要求完成输出。
设函数showNum完成有理数输出：给定整数x、y，输出$\frac{x}{y}$的最简分式。
如果x、y不同号，先输出负号。接着求出x、y的最大公约数g，使x、y分别除以最大公约数，而后输出，即可得到最简分式。
设函数showMultSqrt完成输出$\frac{x}{y}\sqrt{r}$，先根据x、y的符号确定是否输出负号。接着求出x、y的最大公约数g，使x、y分别除以最大公约数，得到a、b，根据题目要求，针对a、b都为1，其中一个为1，和都不为1的情况，按照不同的格式输出。建议使用printf，更方便进行格式化输出。
主函数中每次循环输入一组一元二次方程$a{x}^2+bx+c=0$的系数a、b、c。
如果$a<0$，则将等式两边乘以-1，也就是a、b、c都取自己的相反数，保证$a\ge 0$。只要$a\ge 0$，那么根$\frac{-b+\sqrt{\Delta }}{2a}$一定比根$\frac{-b-\sqrt{\Delta }}{2a}$大。该题要求输出较大根。
为了使$\sqrt{\Delta }$化为最简形式$i\ast \sqrt{r}$，其中r不包含是完全平方数的约数。

• 如果$\Delta$是完全平方数，$\sqrt{\Delta }$就是整数，因此$\frac{-b+\sqrt{\Delta }}{2a}$就是有理数，可以使用输出有理数的函数showNum输出。
• 如果$\Delta$不是完全平方数，
  先使用showNum函数输出有理数$-\frac{b}{2a}$和加号"+"
  ，而后找到$\Delta$的最大的完全平方数约数（i从小到大遍历，找最后一个满足$\Delta$是$i^2$倍数的i），假设找的$\Delta$的约数为$i^2$，$r=\Delta /i^2$那么$\sqrt{\Delta }=i\ast \sqrt{r}$，使用showMultSqrt函数输出$\frac{i}{2a}\sqrt{r}$。

【题解代码】

#include <bits/stdc++.h>
using namespace std;
int gcd(int a, int b)//求a、b的最大公约数 
{
	if(b == 0)
		return a;
	return gcd(b, a%b);
}
void showNum(int x, int y)//输出有理数x/y
{
	if(x*y < 0)
		printf("-");
	int a = abs(x), b = abs(y), g = gcd(a, b);
	a /= g, b /= g;//约分 
	if(b == 1)
		printf("%d", a);
	else
		printf("%d/%d", a, b);
} 
void showMultSqrt(int x, int y, int r)//输出有理数x/y乘以sqrt(r)（保证x不为0，且x*y>0） 
{
	int a = abs(x), b = abs(y), g = gcd(a, b);
	a /= g, b /= g;
	if(a == 1 && b == 1)
		printf("sqrt(%d)", r);
	else if(b == 1)
		printf("%d*sqrt(%d)", a, r); 
	else if(a == 1)
		printf("sqrt(%d)/%d", r, b);
	else
		printf("%d*sqrt(%d)/%d", a, r, b);
}
int maxFac(int x)//求满足i*i是x的约数的最大的i 
{
	for(int i = sqrt(x); i >= 1; --i)
		if(x%(i*i) == 0)
			return i;
} 
void solve(int a, int b, int c)
{
	if(a < 0)//如果a<0，则a、b、c都取相反数，保证a>0 
		a = -a, b = -b, c = -c;
	int delta = b*b-4*a*c;
	if(delta < 0)
		printf("NO");
	else
	{
		int sd = sqrt(delta);//delta开根号的结果
		if(sd*sd == delta)//delta是完全平方数，方程的根中无根号
			showNum(-b+sd, 2*a); 
		else//有根号 
		{
			if(b != 0)//有前一项
			{
				showNum(-b, 2*a);
				printf("+");
			}
			int mf = maxFac(delta);
			showMultSqrt(mf, 2*a, delta/(mf*mf));
		}
	}
	printf("\n");
}
int main()
{
	int t, m, a, b, c;
	scanf("%d %d", &t, &m);
	while(t--)
	{
		scanf("%d %d %d", &a, &b, &c);
		solve(a, b, c);
	}
	return 0;
}