CSP-J2023 T3 uqe题解

· · 个人记录

思路

按照题目思路模拟分解即可，需要注意的是在二次根式中提取开尽方因子的问题。

但是这个题很麻烦，考场我大概调了一坤时过了大样例。

Tip：分数化简的写法（很容易理解，注意异号）：

\begin{aligned} \frac ab=\left\{\begin{matrix} \frac{|a\div \gcd(a,b)|}{|b\div \gcd(a,b)|}(a,b>0 \ \text{或}\ a,b<0) \\ \\-\frac{|a\div \gcd(a,b)|}{|b\div \gcd(a,b)|}(a>0\ \text{且}\ b<0\ \text{或}\ a<0\ \text{且} a>0) \end{matrix}\right.\end{aligned}

大坑！

!注意!，在分解因子时请!注意!时间!复杂度!，这是我的考场代码，复杂度为 O(Tb^2-4Tac)，无法通过20~30分左右的数据点：

 #include <bits/stdc++.h>
using namespace std;
int t,m; 
inline void yls(int u,int d){
    if((u<0&&d>0)||(u>0&&d<0)) cout<<'-';
    if(d/__gcd(u,d)==1) cout<<abs(u/__gcd(u,d));
    else cout<<abs(u/__gcd(u,d))<<'/'<<abs(d/__gcd(u,d));
}
inline bool wqpf(int tr){
    return pow(floor(sqrt(tr)),2)==tr;
}
signed main(){
    ios::sync_with_stdio(0);
    freopen("uqe.in","r",stdin);
    freopen("uqe.out","w",stdout);
    cin>>t>>m;
    for(int i=1,a,b,c;i<=t;i++){
        cin>>a>>b>>c;int tr=b*b-4*a*c;
        if(tr<0) cout<<"NO"<<endl;
        else
            if(wqpf(tr)){
                if((sqrt(tr)-b)/(2*a)>(-sqrt(tr)-b)/(2*a))
                    yls(sqrt(tr)-b,2*a);
                else yls(-sqrt(tr)-b,2*a);
                cout<<endl;
            }
            else{
                if((-b)*1.0/(a*2)) yls(-b,a*2),cout<<'+';
                int ys=1;
                for(int i=1;i<=tr;i++)
                    if(!(tr%i)&&wqpf(i)) ys=max(ys,i); //这里暴力开方浪费了很多时间，考场盲目自信复杂度算错了
                tr/=ys,ys=sqrt(ys);
                if((-sqrt(tr)*ys-b)/(2*a)>(sqrt(tr)*ys-b)/(2*a)) ys=-ys;
                if(ys==a*2) cout<<"sqrt("<<tr<<")"<<endl;
                else if(!(ys%(a*2))) cout<<abs(ys/(a*2))<<"*sqrt("<<tr<<")"<<endl;
                else if(!(a*2%ys)) cout<<"sqrt("<<tr<<")/"<<abs(a*2/ys)<<endl;
                else cout<<abs(ys/__gcd(ys,a*2))<<"*sqrt("<<tr<<")/"<<abs(a*2/__gcd(ys,a*2))<<endl;
            }
    }
    return 0;
}

代码

可以看看注释，非常详细。

#include <bits/stdc++.h>
//修改过的代码，复杂度O(Tb)
using namespace std;
int t,m; 
inline void yls(int u,int d){ //输出分子为u，分母为d的有理分数 
    if((u<0&&d>0)||(u>0&&d<0)) cout<<'-'; //异号，值为负 
    //除gcd可以达到化简分数的效果 
    if(d/__gcd(u,d)==1) cout<<abs(u/__gcd(u,d)); //分母为1，输出整数形式 
    else cout<<abs(u/__gcd(u,d))<<'/'<<abs(d/__gcd(u,d)); //按照分数形式输出 
}
inline bool wqpf(int tr){
    return pow(floor(sqrt(tr)),2)==tr; //判断一个整数tr是否为完全平方数，即为判断根号是否为整 
}
signed main(){
    ios::sync_with_stdio(0);
    freopen("uqe.in","r",stdin);
    freopen("uqe.out","w",stdout); //考试的时候不要写错了啊qwq 
    cin>>t>>m;
    for(int i=1,a,b,c;i<=t;i++){
        cin>>a>>b>>c;int tr=b*b-4*a*c; //计算解的根号部分的被开方数 
        if(tr<0) cout<<"NO"<<endl; //实数范围内无解 
        else
            if(wqpf(tr)){ //根号部分是完全平方数，即有有理数解 
                if((sqrt(tr)-b)/(2*a)>(-sqrt(tr)-b)/(2*a)) //寻找最大解 
                    yls(sqrt(tr)-b,2*a); //套公式即可 
                else yls(-sqrt(tr)-b,2*a);
                cout<<endl;
            }
            else{
                if((-b)*1.0/(a*2)) yls(-b,a*2),cout<<'+';
                // 根据乘法分配律可得(-b+sqrt(tr))/2a=-b/2a-sqrt(tr)/2a
                // 即为输出解的前一项b/2a，为有理数。 
                int ys=1,rr=tr,cnt; //tr为根号下三角形的被开方数，ys为被开方数的最大完全平方因数 
                //rr作临时变量，对根式进行化简，提系数 
                for(int i=2;i*i<=rr;i++)
                    if(!(rr%i)){ //找质因数 
                        cnt=0;
                        while(!(rr%i)) rr/=i,cnt++; //化简至rr与i互质，cnt即为原数所含质因数i的个数 
                        ys*=pow(i,cnt-cnt%2); //提偶数个i出来 
                    }
                tr/=ys,ys=sqrt(ys); //化简，提出来 
                if((-sqrt(tr)*ys-b)/(2*a)>(sqrt(tr)*ys-b)/(2*a)) ys=-ys;
                //如果-b/2a-sqrt(tr)/2a是最大解时，把提出来的系数取负，直接就可以当做-b/2a+sqrt(tr)/2a 
                if(ys==a*2) cout<<"sqrt("<<tr<<")"<<endl;
                //系数为1时，直接输出根号格式 
                else if(!(ys%(a*2))) cout<<abs(ys/(a*2))<<"*sqrt("<<tr<<")"<<endl;
                //系数为整数时。注意：可以证明 sqrt(tr)/2a 一定为整，为了方便符号处理，直接取绝对值就好了 
                else if(!(a*2%ys)) cout<<"sqrt("<<tr<<")/"<<abs(a*2/ys)<<endl;
                //系数分子为1，当作除法处理 
                else cout<<abs(ys/__gcd(ys,a*2))<<"*sqrt("<<tr<<")/"<<abs(a*2/__gcd(ys,a*2))<<endl;
                //系数为分数时，按照题面格式输出为a*sqrt(c)/b的格式    
            }
    }
    return 0;
}