万能的高精度模板
该重载的运算符都重载了，赋值、强制类型转换都没问题。输入输出可以直接用 cin,cout。
自带压位优化。
唯一的区别是，没有取模运算，除法会返回 pair<结果,余数>。
class Int {
public:
using ll = long long;
Int() {};
Int(const string& s);
Int(ll a) :Int(to_string(a)) {}
Int(const Int& bInt) :nums(bInt.nums), isPositive(bInt.isPositive), length(bInt.length) {}
Int(Int&& bInt) noexcept :nums(move(bInt.nums)), isPositive(bInt.isPositive), length(bInt.length) {}
Int(const vector<int>& vec, bool sign = true) :nums(vec), isPositive(sign) { cutLeadZero(); }
friend istream& operator >>(istream& is, Int& bInt) {
string s;
is >> s;
bInt = move(Int(s));
return is;
}
friend ostream& operator <<(ostream& os, const Int& bInt);
operator string() const;
const Int& operator +() const { return *this; }
Int operator -() const {
Int tmp(*this);
if (!tmp.isZero())
tmp.isPositive = !isPositive;
return tmp;
}
bool operator <(const Int& bInt) const;
bool operator <=(const Int& bInt) const;
bool operator ==(const Int& bInt) const;
Int operator +(const Int& bInt) const;
Int operator -(const Int& bInt) const;
Int operator *(const Int& bInt) const;
// 除法会返回 商和余数
pair<Int, Int> operator /(const Int& bInt) const;
int operator[](int idx) const { return nums[idx]; }
Int& operator =(const Int& bInt) {
if (bInt == *this)
return *this;
nums = bInt.nums;
isPositive = bInt.isPositive;
length = bInt.length;
return *this;
}
Int& operator =(Int&& bInt)noexcept {
nums = move(bInt.nums);
isPositive = bInt.isPositive;
length = bInt.length;
return *this;
}
size_t size() const { return nums.size(); }
void cutLeadZero();
bool isZero() const;
Int absValue() const {
return move(Int(nums));
}
static Int e(size_t n) {
if (n <= 0)
return move(Int(vector<int>(1, 1)));
int m = n / digit;
n -= m * digit;
vector<int> ans(m);
string s = "1";
s += move(string(n, '0'));
ans.push_back(stoi(s));
return move(Int(ans));
}
private:
// 低位到高位
vector<int> nums;
bool isPositive = 1;
int length = 0;
static int digit;
static int mod;
};
int Int::digit = 8;
int Int::mod = 100000000;
Int::Int(const string& s) {
int n = s.size(), minIdx = 0;
if(s[0]=='-')
isPositive = false, minIdx = 1;
else if(s[0]=='+')
isPositive = true, minIdx = 1;
for (int i = n - 1; i >= minIdx; i -= digit) {
int beg = max(minIdx, i - digit + 1);
nums.push_back(stoi(s.substr(beg, i - beg + 1)));
}
cutLeadZero();
}
ostream& operator <<(ostream& os, const Int& bInt) {
os << (string)bInt;
return os;
}
Int::operator string() const {
string ans;
if (!isPositive)
ans += "-";
int n = nums.size();
for (int i = n - 1; i >= 0; i--) {
string s = to_string(nums[i]);
if (i != n - 1)
ans += string(digit - s.size(), '0');
ans += s;
}
return ans;
}
bool Int::operator<(const Int& bInt) const {
if (isPositive && !bInt.isPositive)
return false;
if (!isPositive && bInt.isPositive)
return true;
bool flag = true;
if (!isPositive)
flag = false;
if (length < bInt.length)
return flag;
else if (length > bInt.length)
return !flag;
int n = size();
for (int i = n - 1; i >= 0; i--) {
if (nums[i] < bInt[i])
return flag;
else if (nums[i] > bInt[i])
return !flag;
}
return false;
}
bool Int::operator<=(const Int& bInt) const {
if (isPositive && !bInt.isPositive)
return false;
if (!isPositive && bInt.isPositive)
return true;
bool flag = true;
if (!isPositive)
flag = false; // 都为负数
if (length < bInt.length)
return flag;
else if (length > bInt.length)
return !flag;
int n = size();
for (int i = n - 1; i >= 0; i--) {
if (nums[i] < bInt[i])
return flag;
else if (nums[i] > bInt[i])
return !flag;
}
return true;
}
bool Int::operator==(const Int& bInt) const {
if (length != bInt.length)
return false;
int n = size();
for (int i = 0; i < n; i++)
if (nums[i] != bInt[i])
return false;
return true;
}
Int Int::operator+(const Int& bInt) const {
if (!bInt.isPositive)
return *this - (-bInt);
if (!isPositive)
return bInt - (-*this);
vector<int> ans;
int n = size(), m = bInt.size(), sum = 0, i = 0, j = 0;
while (i < n || j < m || sum)
{
if (i < n)
sum += nums[i++];
if (j < m)
sum += bInt[j++];
ans.push_back(sum % mod);
sum /= mod;
}
return move(Int(ans, isPositive));
}
Int Int::operator-(const Int& bInt) const
{
if (!bInt.isPositive)
return *this + (-bInt);
if (!isPositive)
return -((-*this) + bInt);
if (*this < bInt)
return -(bInt - *this);
vector<int> ans;
int i = 0, j = 0, n = size(), m = bInt.size(), sum = 0;
while (i < n || j < m || sum) {
if (i < n)
sum += nums[i++];
if (j < m)
sum -= bInt[j++];
int flag = 0;
if (sum < 0) {
flag = -1;
sum += mod;
}
ans.push_back(sum);
sum = flag;
}
return move(Int(ans));
}
Int Int::operator*(const Int& bInt) const {
int n = size(), m = bInt.size();
vector<int> ans(n + m);
using ll = long long;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
ll tmp = ans[i + j] + nums[i] * 1ll * bInt[j];
ans[i + j] = tmp % mod;
ans[i + j + 1] += tmp / mod;
}
}
return move(Int(ans, isPositive == bInt.isPositive));
}
pair<Int, Int> Int::operator/(const Int& bInt) const {
Int a = absValue();
Int b = bInt.absValue();
if (b.isZero())
return pair<Int, Int>(*this, move(b));
if (a < b)
return pair<Int, Int>(move(Int(0)), *this);
int len = a.length - b.length + 1;
string ans;
if (isPositive != bInt.isPositive)
ans = "-";
for (int i = 0; i < len; i++) {
Int tmp = e(len - i - 1) * b;
int times = 0;
while (tmp <= a) {
a = a - tmp;
++times;
}
ans += times + '0';
}
a.isPositive = isPositive;
return pair<Int, Int>(move(Int(ans)), move(a));
}
void Int::cutLeadZero() {
while(nums.size() > 1 && nums.back() == 0)
nums.pop_back();
if(nums.empty()) length = 0;
else length = (nums.size() - 1) * digit + to_string(nums.back()).size();
}
bool Int::isZero() const {
return nums.size() == 1 && nums.back() == 0;
}