记录编号	569294	评测结果	AAAAAAAAAA
题目名称	[NOIP 2011]大整数开方	最终得分	100
用户昵称	lihaoze	是否通过	通过
代码语言	C++	运行时间	2.491 s
提交时间	2022-02-28 22:43:13	内存使用	5.89 MiB

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <cstring>
#define ABS(_x) ((_x) < 0 ? -(_x) : (_x))
#define OPEN(_x) freopen(#_x".in", "r", stdin); freopen(#_x".out", "w", stdout)

using namespace std;

typedef unsigned long long ll;

struct Bigint {
    vector<int> num;
    Bigint () {;}
    Bigint (int rst) {
        num.clear();
        while(rst) {
            num.emplace_back(rst % 10);
            rst /= 10;
        }
    }
    Bigint (const char* rst) {
        num.clear();
        int len = strlen(rst);
        for(register int i = len-1; i>=0; --i) num.emplace_back(rst[i]-48);
    }
    Bigint operator + (const Bigint& rst) {
        Bigint ret;
        int t = 0;
        for(register int i = 0; i<(int)num.size() || i<(int)rst.num.size() || t; ++i) {
            if(i<(int)num.size()) t += num[i];
            if(i<(int)rst.num.size()) t += rst.num[i];
            ret.num.emplace_back(t % 10);
            t /= 10;
        }
        return ret;
    }
    Bigint operator += (Bigint rst) {
        *this = *this + rst;
        return *this;
    }
    Bigint operator * (int rst) {
        Bigint ret;
        int t = 0;
        for(register int i = 0; i<(int)num.size() || t; ++i) {
            if(i<(int)num.size()) t += num[i] * rst; 
            ret.num.emplace_back(t % 10);
            t /= 10;
        }
        while(ret.num.size() > 1 && !ret.num.back()) ret.num.pop_back();
        return ret;
    }
    Bigint operator - (int rst) {
        Bigint ret(*this);
        ret.num[0]--;
        int len = ret.num.size();
        for(register int i = 0; i<len-1; ++i) {
            if(ret.num[i] < 0) ret.num[i] = 9, ret.num[i+1]--;
        }
        while(ret.num.size() > 1 && !ret.num.back()) ret.num.pop_back();
        return ret;
    }
    Bigint operator * (Bigint& rst) {
        Bigint ret;
        for(register int i = rst.num.size()-1; i>=0; --i) {
            ret = ret * 10;
            ret += *this * rst.num[i];
        }
        return ret;
    }
    template <typename T> Bigint operator *= (T &rst) {
        *this = *this * rst;
        return *this;
    }
    template <typename T> bool operator < (T &rst) {
        auto tmp = Bigint (rst);
        if(num.size() > tmp.num.size()) return 0;
        else if(num.size() < tmp.num.size()) return 1;
        else {
            for(register int i = num.size()-1; i>=0; --i) {
                if(num[i] < tmp.num[i]) return 1;
                if(num[i] > tmp.num[i]) return 0;
            }
        }
        return 0;
    }
    template <typename T> bool operator == (T &rst) {
        auto tmp = Bigint (rst);
        return num == tmp.num;
    }
    template <typename T> bool operator > (T &rst) {
        auto tmp = Bigint (rst);
        if(*this == tmp || *this < tmp) return 0;
        return 1;
    }
    template <typename T> bool operator >= (T &rst) {
        return *this > rst || *this == rst;
    } 
    template <typename T> bool operator <= (T &rst) {
        return *this < rst || *this == rst;
    }
};

ostream& operator << (ostream& os, Bigint& rst) {
    for(register int i = rst.num.size()-1; i>=0; --i) os << rst.num[i];
    return os;
}

Bigint& operator >> (istream& is, Bigint& rst) {
    rst.num.clear();
    string str;
    is >> str;
    rst = str.c_str();
    return rst;
}

inline Bigint div2(Bigint A) {
    for(register int i = A.num.size()-1; i>0; --i) {
        A.num[i-1] += (A.num[i] % 2) * 10;
        A.num[i] >>= 1;
    }
    A.num[0] >>= 1;
    while(A.num.size() > 1 && !A.num.back()) A.num.pop_back();
    return A;
}

int main() {
    #ifdef DEBUG
    OPEN(test);
    #endif
    OPEN(hugeint);
    ios::sync_with_stdio(false), cin.tie(0);
    Bigint n;
    cin >> n;
    Bigint l = "1", r = "1000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000";
    while(l < r) {
        Bigint mid = div2(l+r+1);
        if(mid*mid <= n) l = mid;
        else r = mid-1;
    }
    cout << r << '\n';
    return 0;
}