CSP-J 2023 T3 表达式 题解

· · 题解

Solution

CCF 特有的今年 T3 大模拟（

良心题目，甚至给了你一元二次方程的判别式（）。

按题意模拟即可。

当 \Delta < 0 时，输出 \texttt{NO}。

当 \Delta = 0 时，只有一个解，即为 \dfrac{-b}{2a}，约分后按要求输出即可。

约分过程：若要对 \dfrac{-b}{2a} 进行约分，求出 d = \gcd(|b|,|2a|)，约分后的分数即为 \dfrac{(-b)\div d}{2a\div d}。

当 \Delta > 0 时，分类讨论：

同样对分数约分后输出即可。

至于 r 的求法：由于 M\le 1000, \Delta \le 5\times M^2，暴力枚举 1\dots \left\lfloor\sqrt{\Delta}\right\rfloor 即可。

时间复杂度为 \mathcal{O}(TM) 左右。（\gcd 复杂度忽略不计）

Code

#include<bits/stdc++.h>
#define ll long long
using namespace std;
inline ll read(){
    ll x=0,y=1;
    char c=getchar();
    while(c<'0'||c>'9'){
        if(c=='-')y=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9')x=(x<<3)+(x<<1)+c-'0',c=getchar();
    return x*y;
}
ll T,M,a,b,c,delta;
ll gcd(ll a,ll b){
    if(b==0)return a;
    return gcd(b,a%b);
}
int main(){
    T=read();M=read();
    while(T--){
        a=read();b=read();c=read();
        delta=b*b-4*a*c;
        if(delta<0){
            printf("NO\n");
        }else if(delta==0){
            ll p=-b,q=2*a;
            ll pq=gcd(abs(q),abs(p));
            p/=pq,q/=pq;
            if(q<0)q=-q,p=-p;
            if(q==1)printf("%lld\n",p);
            else printf("%lld/%lld\n",p,q);
        }else{
            ll p=-b,q=2*a;
            ll sq=(ll)sqrt(delta);
            if(sq*sq==delta){
                if(q>0)p+=sq;
                else p-=sq;
                ll pq=gcd(abs(q),abs(p));
                p/=pq,q/=pq;
                if(q<0)q=-q,p=-p;
                if(q==1)printf("%lld\n",p);
                else printf("%lld/%lld\n",p,q);
            }else{
                ll pq=gcd(abs(q),abs(p));
                p/=pq,q/=pq;
                if(q<0)q=-q,p=-p;
                if(p!=0){
                    if(q==1)printf("%lld+",p);
                    else printf("%lld/%lld+",p,q);
                }
                q=abs(2*a);
                p=1;
                ll t=0;
                for(int r=sq;r>=1;r--)
                    if(delta%(r*r)==0){
                        p*=r;
                        t=delta/(r*r);
                        break;
                    }
                pq=gcd(abs(q),abs(p));
                p/=pq,q/=pq;
                if(q<0)q=-q,p=-p;
                if(p==q) printf("sqrt(%lld)\n",t);
                else if(q==1) printf("%lld*sqrt(%lld)\n",p,t);
                else if(p==1) printf("sqrt(%lld)/%lld\n",t,q);
                else printf("%lld*sqrt(%lld)/%lld\n",p,t,q);
            }
        }
    }
    return 0;
}