题目链接

https://www.dotcpp.com/oj/problem1450.html

解题思路

不知道你有没有想到一道题https://www.dotcpp.com/oj/problem1492.html
异曲同工
大佬讲解思路
这位大佬讲针不戳！！
可以看看大佬的思路，看看我讲的代码！
揪出本质，是在考察如何实现高精度开二次根。
那我们就来絮叨絮叨开二次方根的代码理解。
核心代码三部分：

//高精度乘法
//正常的高精度乘法的板子
string large_mul(string ts1,string ts2){
    string res;
    int a[N],b[N],c[N];
    memset(a,0,sizeof a);//没有直接error！！！ 
    memset(b,0,sizeof b);//没有直接error！！！
    memset(c,0,sizeof c);//没有直接error！！！    
    int len1=ts1.length();
    int len2=ts2.length();
    //逆置
    for(int i=0;i<len1;i++)
        a[len1-i-1]=ts1[i]-'0';
    for(int i=0;i<len2;i++)
        b[len2-i-1]=ts2[i]-'0';
    //乘法核心代码
    for(int i=0;i<len1;i++)    
        for(int j=0;j<len2;j++){
            c[i+j]+=a[i]*b[j];
            c[i+j+1]+=c[i+j]/10;
            c[i+j]%=10;
        }
    int len=len1+len2-1;
    if(c[len]!=0) len++;
    //逆置并转换成字符串
    for(int i=len-1;i>=0;i--)
        res+=c[i]+'0';

    return res;
}

//高精度开根（！！！重点！！！）
string large_sqrt(string a){
    string res;
    int len=a.length();
    int tlen=len/2;
    if(len&1){//奇数 
        for(int i=0;i<tlen+1;i++){
            for(int j=0;j<=9;j++){
                string tmpstr=res;
                tmpstr+=j+'0';
                if(large_cmp(large_mul(tmpstr,tmpstr),a,2*(tlen-i))){//大于了要被开根的数，则让res拼接上前一个j//cmp的参数下面讲解
                    res+=j-1+'0';
                    break;
                }
                if(j==9) res+='9';//前面一直没找到大于被开根的数，拼接上9
            }
        }
    }
    else{
        for(int i=0;i<tlen;i++){
            for(int j=0;j<=9;j++){
                string tmpstr=res;
                tmpstr+=j+'0';
                if(large_cmp(large_mul(tmpstr,tmpstr),a,2*(tlen-1-i))){
                    res+=j-1+'0';
                    break;
                }
                if(j==9) res+='9';
            }
        }
    }
    return res;
}

//高精度比较（！！！重点！！！）
bool large_cmp(string a,string b,int rest){//a是我们尝试去相乘的两个数的积，b是被开根数，rest是a剩下的几位，剩下的几位暂时为0
    int alen=a.length();
    int blen=b.length();
    if(blen<alen+rest) return true;//算出的两数积长度大于被开根数
    if(blen>alen+rest) return false;//算出的两数积长度小于被开根数
    for(int i=0;i<blen;i++){
        if(a[i]-'0'>b[i]-'0') return true;//同一位置，a的数大
        if(a[i]-'0'<b[i]-'0') return false;//同一位置，a的数小
    }
    return false;//如果完全相同，返回假，，因为我们上面比较判断之后res拼接的是j的前一个数
}

//至此，难点和核心都讲完了，确实挺难一下理解透彻的

AC代码

#include<bits/stdc++.h>
using namespace std;
const int N=1010;

string large_mul(string ts1,string ts2){
    string res;
    int a[N],b[N],c[N];
    memset(a,0,sizeof a);//没有直接error！！！ 
    memset(b,0,sizeof b);//没有直接error！！！
    memset(c,0,sizeof c);//没有直接error！！！    
    int len1=ts1.length();
    int len2=ts2.length();

    for(int i=0;i<len1;i++)
        a[len1-i-1]=ts1[i]-'0';
    for(int i=0;i<len2;i++)
        b[len2-i-1]=ts2[i]-'0';

    for(int i=0;i<len1;i++)    
        for(int j=0;j<len2;j++){
            c[i+j]+=a[i]*b[j];
            c[i+j+1]+=c[i+j]/10;
            c[i+j]%=10;
        }
    int len=len1+len2-1;
    if(c[len]!=0) len++;

    for(int i=len-1;i>=0;i--)
        res+=c[i]+'0';

    return res;
}

bool large_cmp(string a,string b,int rest){
    int alen=a.length();
    int blen=b.length();
    if(blen<alen+rest) return true;
    if(blen>alen+rest) return false;
    for(int i=0;i<blen;i++){
        if(a[i]-'0'>b[i]-'0') return true;
        if(a[i]-'0'<b[i]-'0') return false;
    }
    return false;
}

string large_sqrt(string a){
    string res;
    int len=a.length();
    int tlen=len/2;
    if(len&1){//奇数 
        for(int i=0;i<tlen+1;i++){
            for(int j=0;j<=9;j++){
                string tmpstr=res;
                tmpstr+=j+'0';
                if(large_cmp(large_mul(tmpstr,tmpstr),a,2*(tlen-i))){
                    res+=j-1+'0';
                    break;
                }
                if(j==9) res+='9';
            }
        }
    }
    else{
        for(int i=0;i<tlen;i++){
            for(int j=0;j<=9;j++){
                string tmpstr=res;
                tmpstr+=j+'0';
                if(large_cmp(large_mul(tmpstr,tmpstr),a,2*(tlen-1-i))){
                    res+=j-1+'0';
                    break;
                }
                if(j==9) res+='9';
            }
        }
    }
    return res;
}

int main(){
    string s1,s2;
    cin>>s1>>s2;

    cout<<large_mul(large_sqrt(s1),large_sqrt(s2));
} 

总结

理解了一下午+半晚上，多温习才能记熟！