比赛 防止颓废的小练习v0.2 评测结果 AAAAAAAAAA
题目名称 大整数开方 最终得分 100
用户昵称 KZNS 运行时间 0.124 s
代码语言 C++ 内存使用 0.29 MiB
提交时间 2016-10-18 10:05:58
显示代码纯文本
//KZNS
#include <cstdio>
#include <string>
#include <cstring>
using namespace std;
class poi {
    public:
        int A[300];
    void a0() {
        memset(A, 0, sizeof(A));
    }
    void carry() {
        for (int i = 0; i <= 250; i++) {
            A[i+1] += A[i] / 10;
            A[i] %= 10;
        }
    }
    void pf() {
        int i = 250;
        for (; i > 1; i--)
            if (A[i])
                break;
        for (; i >= 0; i--)
            printf("%d", A[i]);
    }
};
poi operator + (const poi &a, const poi &b) {
    poi c;
    c.a0();
    for (int i = 0; i <= 250; i++)
        c.A[i] = a.A[i] + b.A[i];
    c.carry();
    return c;
}
poi operator * (const poi &a, const poi &b) {
    poi c;
    c.a0();
    for (int i = 0; i <= 250; i++)
        for (int j = 0; j <= 250; j++)
            c.A[i+j] += a.A[i] * b.A[j];
    c.carry();
    return c;
}
bool operator <= (const poi &a, const poi &b) {
    for (int i = 250; i >= 0; i--) {
        if (a.A[i] == b.A[i])
            continue;
        else if (a.A[i] < b.A[i])
            return true;
        else
            return false;
    }
    return true;
}
poi operator - (poi a, const poi &b) {
    for (int i = 0; i <= 250; i++) {
        if (a.A[i] < b.A[i]) {
            a.A[i+1]--;
            a.A[i] = a.A[i] + 10 - b.A[i];
        }
        else
            a.A[i] -= b.A[i];
    }
    return a;
}
poi operator / (poi a, const int &b) {
    for (int i = 250; i > 0; i--) {
        a.A[i-1] += a.A[i] % 2 * 10;
        a.A[i] /= 2;
    }
    a.A[0] /= 2;
    return a;
}
poi NB;
void rin() {
    char S[103];
    scanf("%s", S);
    int N = strlen(S);
    NB.a0();
    for (int i = 0; i < N; i++)
        NB.A[i] = S[N-1-i] - '0';
}
int main() {
    freopen("hugeint.in", "r", stdin);
    freopen("hugeint.out", "w", stdout);
    rin();
    poi l, r, md;
    poi lll;
    lll.a0();
    lll.A[0] = 1;
    l.a0();
    r = NB;
    while (!(r - l <= lll)) {
        md = (l + r) / 2;
        if (md * md <= NB)
            l = md;
        else
            r = md;
    }
    l.pf();
    return 0;
}
//UBWH