大整数开方

lfcemy · 2020-12-12 12:35:39 · 个人记录

1. 高精度比较、乘法模板
2. 模拟答案

• 算法：高精度、二分
• 时间复杂度：O(n^3)

#include"cstdio"
#include"cstring"
using namespace std;
struct S {
    int x,y[109];
    S() {
        x=1;
        memset(y,0,sizeof y);
    }
    void read() {
        char a[109];
        scanf("%s",a);
        x=strlen(a);
        for(int i(x); i; --i) {
            y[i]=a[x-i]^48;
        }
    }
    void print() {
        x-=!y[x];
        for(int i(x); i; --i) {
            putchar(48+y[i]);
        }
    }
    bool operator<(S b) {
        if(x>b.x) {
            return false;
        }
        for(int i(b.x); i; --i) {
            if(y[i]==b.y[i]) {
                continue;
            }
            return y[i]<b.y[i];
        }
        return 0;
    }
    S operator*(S b) {
        S c;
        c.x=x+b.x-1;
        for(int i(1); i<=x; ++i) {
            for(int j(1); j<=b.x; ++j) {
                c.y[i+j-1]+=y[i]*b.y[j];
                c.y[i+j]+=c.y[i+j-1]/10;
                c.y[i+j-1]%=10;
            }
        }
        c.x+=c.y[c.x+1]>0;
        return c;
    }
} n,m;
int main() {
    n.read();
    m.x=(n.x>>1)+(n.y[1]&1);
    for(int i(m.x); i; --i) {
        m.y[i]=9;
        while(n<m*m) {
            --m.y[i];
        }
    }
    m.print();
}