记录编号 |
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;
}