/**
只考虑正数[1, +∞);
“-”运算只允许大数减小数;
小端存储；
*/
typedef struct BigInteger0 {
vector<int> v;
BigInteger0(int len) {
v.resize(len);
}
BigInteger0(const vector<int>& nv) {
v.assign(nv.begin(), nv.end());
}
BigInteger0(const char str[]) {
int len = strlen(str);
v.resize(len);
; i < len; ++i)
v[len - - i] = str[i] - ';
}
BigInteger0 operator + (const BigInteger0& obj) const {
BigInteger0 res(v);
int len = max(v.size(), obj.v.size());
res.v.resize(len + );
; i < len; ++i) {
if(i < obj.v.size())res.v[i] += obj.v[i];
) {
res.v[i + ] += res.v[i] / ;
res.v[i] %= ;
}
}
] == )res.v.resize(res.v.size() - );
return res;
}
/*默认v > obj，即v.size() > obj.v.size()*/
BigInteger0 operator - (const BigInteger0& obj) const {
BigInteger0 res(v);
; i < v.size(); ++i) {
if(i < obj.v.size())res.v[i] -= obj.v[i];
) {
res.v[i + ]--;
res.v[i] += ;
}
}
int len = res.v.size();
] == ; --len);
res.v.resize(len);
return res;
}
BigInteger0 operator * (const BigInteger0& obj) const {
BigInteger0 res(v.size() + obj.v.size());
, len1 = v.size(); i < len1; ++i) {
, len2 = obj.v.size(); j < len2; ++j) {
res.v[i + j] += v[i] * obj.v[j];
) {
res.v[i + j + ] += res.v[i + j] / ;
res.v[i + j] %= ;
}
}
}
int len = res.v.size();
] == ; --len);
res.v.resize(len);
return res;
}
BigInteger0 operator / (BigInteger0& obj) const {
");
");
else {
BigInteger0 res("), tmp(v);
while(tmp > obj) {
int lendif = tmp.v.size() - obj.v.size();
BigInteger0 b1 = ten ^ lendif;
BigInteger0 b2 = b1 * obj;
if(tmp < b2) {
b1 = ten ^ (lendif - );
b2 = b1 * obj;
}
while(tmp >= b2) {
tmp = tmp - b2;
res = res + b1;
}
}
return res;
}
}
/**power*/
BigInteger0 operator ^ (int n) const {
BigInteger0 res("), tmp(v);
; n >>= ) {
)res = res * tmp;
tmp = tmp * tmp;
}
return res;
}
BigInteger0 sqrt() {
) / ;
BigInteger0 res(len), ten(");
; i >= ; --i) {
, high = , mid, bit;
) {
mid = (low + high) >> ;
BigInteger0 b = res + (BigInteger0(vector<, mid)) * (ten ^ i));
if(b * b <= *this) {
low = mid;
bit = mid;
}
else high = mid;
}
res.v[i] = bit;
}
] == ; --len);
res.v.resize(len);
return res;
}
bool operator < (const BigInteger0& obj) const {
if(v.size() < obj.v.size())return true;
else if(v.size() > obj.v.size())return false;
else {
;
&& v[i] == obj.v[i]; --i);
)return false;
else return v[i] < obj.v[i];
}
}
bool operator > (const BigInteger0& obj) const {
return obj < *this;
}
bool operator == (const BigInteger0& obj) const {
if(v.size() != obj.v.size())return false;
else {
; i < v.size(); ++i) {
if(v[i] != obj.v[i])return false;
}
return true;
}
}
bool operator >= (const BigInteger0& obj) const {
return *this > obj || *this == obj;
}
bool operator <= (const BigInteger0& obj) const {
return *this < obj || *this == obj;
}
string value() {
string res;
; i >= ; --i)res.push_back(v[i] + ');
)res.push_back(');
return res;
}
} BigInteger;
V2.0
/**
只考虑正数[1, +∞);
“-”运算只允许大数减小数;
小端存储；
*/
typedef struct BigInteger0 {
typedef long long LL;
, BOUND = int(1e9);
vector<LL> v;
void trim() {
;
&& v[i] == ; --i);
)v.resize(i + );
}
string value() {
];
string res;
trim();
)res.push_back(');
else {
; i >= ; --i) {
)sprintf(tmp, "%I64d", v[i]);
else sprintf(tmp, "%09I64d", v[i]);
res += string(tmp);
}
}
return res;
}
bool isEven(){
] % == ;
}
BigInteger0(const vector<LL>& nv): v(nv) {}
BigInteger0(int len) {
v.resize(len);
}
BigInteger0(const char str[]) {
int len = strlen(str);
, cnt = , last = len;
v.resize(cap);
, len - BIT); i >= ; i = max(, i - BIT)) {
LL tmp = ;
for(int j = i; j < last; ++j) {
tmp = tmp * + str[j] - ';
}
v[cnt++] = tmp;
last = i;
)break;
}
trim();
}
BigInteger0 operator + (const BigInteger0& obj) const {
BigInteger0 res(v);
int len = max(v.size(), obj.v.size());
res.v.resize(len + );
; i < len; ++i) {
if(i < obj.v.size())res.v[i] += obj.v[i];
if(res.v[i] >= BOUND) {
res.v[i + ] += res.v[i] / BOUND;
res.v[i] %= BOUND;
}
}
res.trim();
return res;
}
/*默认v >= obj，即v.size() >= obj.v.size()*/
BigInteger0 operator - (const BigInteger0& obj) const {
BigInteger0 res(v);
; i < v.size(); ++i) {
if(i < obj.v.size())res.v[i] -= obj.v[i];
) {
res.v[i + ]--;
res.v[i] += BOUND;
}
}
res.trim();
return res;
}
BigInteger0 operator * (const BigInteger0& obj) const {
BigInteger0 res(v.size() + obj.v.size());
, len1 = v.size(); i < len1; ++i) {
, len2 = obj.v.size(); j < len2; ++j) {
res.v[i + j] += v[i] * obj.v[j];
if(res.v[i + j] >= BOUND) {
res.v[i + j + ] += res.v[i + j] / BOUND;
res.v[i + j] %= BOUND;
}
}
}
res.trim();
return res;
}
BigInteger0 divide(const BigInteger0& obj, BigInteger0& reminder){
BigInteger0 zero(");
if(*this < obj){reminder = *this; return zero;}
else if(*this == obj){reminder = zero; return one;}
else{
BigInteger0 tmp(v), p1 = one, p2 = one, res = zero;
while(tmp >= obj){
p1 = one;
while(p1 * obj <= tmp){
p2 = p1;
p1 = p1 * two;
}
res = res + p2;
tmp = tmp - (obj * p2);
}
reminder = tmp;
return res;
}
}
BigInteger0 operator / (const BigInteger0& obj){
BigInteger0 rem(");
return this->divide(obj, rem);
}
BigInteger0 operator % (const BigInteger0& obj){
BigInteger0 rem(");
this->divide(obj, rem);
return rem;
}
/**power*/
BigInteger0 operator ^ (BigInteger0 n) const {
BigInteger0 zero(");
BigInteger0 res("), tmp(v);
for(; n > zero; n = n / two) {
if(!n.isEven())res = res * tmp;
tmp = tmp * tmp;
}
return res;
}
bool operator < (const BigInteger0& obj) const {
if(v.size() < obj.v.size())return true;
else if(v.size() > obj.v.size())return false;
else {
;
&& v[i] == obj.v[i]; --i);
)return false;
else return v[i] < obj.v[i];
}
}
bool operator > (const BigInteger0& obj) const {
return obj < *this;
}
bool operator == (const BigInteger0& obj) const {
if(v.size() != obj.v.size())return false;
else {
; i < v.size(); ++i) {
if(v[i] != obj.v[i])return false;
}
return true;
}
}
bool operator >= (const BigInteger0& obj) const {
return *this > obj || *this == obj;
}
bool operator <= (const BigInteger0& obj) const {
return *this < obj || *this == obj;
}
BigInteger0& operator = (const BigInteger0& obj) {
v.assign(obj.v.begin(), obj.v.end());
return *this;
}
} BigInteger;