P9750题解

· · 题解

场上唯一没挂的题，竟然还是大模拟，代码八九十行，接下来慢慢讲。

题目传送门

题目大意

求解形如 ax^2+bx+c=0 的一元二次方程，无实数解输出 NO，有实数解输出较大的那个，但需要按照一定格式输出，也就是 q1+q2\sqrt{r}，其中所有有理数需要表示成 \frac{p}{q} 且 \gcd(p,q)=1，能化简的要化简，具体地讲就是分母为 1 的要化成整数，分子为 0 的要舍去，根号下可以拆成 \sqrt{a_1^2a_2^2\cdots a_n^2b} 的要化成 a_1a_2\cdots a_n\sqrt{b}。
这样讲有点绕，具体可以看原题描述。
其中 ax^2+bx+c=0 的两个解 x_{1,2}=\frac{-b\pm\sqrt{\Delta}}{2a}，其中 \Delta=b^2-4ac。
显然，若 \Delta<0，该方程无实数解。

解题思路

既然是模拟，按照题意模拟即可，麻烦在输出。
注意坑点：很多人以为取较大的解就是取 \frac{-b+\sqrt{\Delta}}{2a}，但当 2a<0 时，应当取 \frac{-b-\sqrt{\Delta}}{2a}，这一点在赛时很可能卡住了无数选手。
具体思路在这里讲太麻烦，看代码吧，但有点长。

完整代码（赛时）

#include <bits/stdc++.h>
using namespace std;
int t,m,a,b,c,delta;
void you(int delta)//处理有理数输出
{
    int p=-b+sqrt(delta),w=-b-sqrt(delta);//计算两个解的分子
    int q=2*a;//计算分母
    if (p*1.0/q<w*1.0/q) p=w;//取较大解

    if (p%q==0 && w%q==0)//如果整除直接输出p/q
    {
        cout<<p/q;
        return;
    }
    if ((p<0 && q>0) || (p>0 && q<0)) cout<<'-';//如果为负输出负号
    p=abs(p);
    q=abs(q);//取绝对值
    int k=__gcd(p,q);//求最大公因数

    p/=k;
    q/=k;//约分
    if (q==1) cout<<p;//如果分母为1直接输出分子
    else if (p==0) cout<<0;//如果分子为0直接输出0
    else printf("%d/%d",p,q);//否则输出p/q的形式
}
int f(int delta)//化简根号，如果根号下的数的因子中有完全平方数，则可以将其分离出来
{
    int ans=1;
    for (int i=2;i*i<=delta;i++)
        while(delta%(i*i)==0)
        {
            ans*=i;
            delta/=i*i;
        }
    return ans;
}
void wu(int delta)//处理无理数输出
{
    if (-b*1.0/(2*a))//如果q1不等于0
    {
        you(0);//按有理数输出q1
        cout<<'+';//记得输出一个加号
    }
    int k=f(delta);//计算根号化简后的系数
    delta/=k*k;//根号下的数要除以k^2
    double q2=fabs(1.0*k/(2*a));//计算q2
    if (q2==1) printf("sqrt(%d)",delta);//如果等于1直接省略
    else if (q2==floor(q2)) printf("%.0f*sqrt(%d)",q2,delta);//如果是整数直接保留小数点0位输出
    else if (1/q2==floor(1/q2) && 1/q2!=0) printf("sqrt(%d)/%.0f",delta,1/q2);//如果1/q2是整数，那么将q2作为分母输出，具体见题意
    else//否则按照有理数输出q2
    {
        int c=k;
        int d=2*a;
        int x=__gcd(c,d);
        c/=x;
        d/=x;
        if ((c<0 && d>0) || (c>0 && d<0))
        {
            c=abs(c);
            d=abs(d);
        }
        if (c!=1) cout<<abs(c)<<'*';//注意输出乘号，与平常数学中不同
        printf("sqrt(%d)/%d",delta,d);
    }
    cout<<endl;
}
int main()
{
    //freopen("uqe.in","r",stdin);
    //freopen("uqe.out","w",stdout);
    cin>>t>>m;
    while(t--)
    {
        cin>>a>>b>>c;
        delta=b*b-4*a*c;//计算delta
        if (delta<0) cout<<"NO"<<endl;//如果小于0说明没有实数解
        else
        {
            if (sqrt(delta)==floor(sqrt(delta)))//由于保证delta是整数，如果根号下delta是整数，按照有理数输出
            {
                you(delta);
                cout<<endl;
            }
            else wu(delta);//否则按照无理数输出
        }
    }
    return 0;//完结撒花
}