C++ 最好用的BigInteger大整数类实现 For OIer
2022.3.19 (Ver 5)
2022.7.3 Updated (Ver 5.1)
Ver 5.2: 改正自减运算后置的返回值。
Ver 5.1: 改正BigInteger::pow函数的bug。旧代码已经被替换。
如何使用BigInteger?（下文中所有BigInteger都能用BigInt代替）。
无论您想要用BigInteger的哪一部分功能，请把整个模板（在文章最后面）放在cpp文件的最前面。
模板已经顺利通过当前的所有C++标准（C++20及以前） 。 代码中所有A变量的类型都为BigInteger，B变量的类型可为BigInteger，int，long long int，const char *，string中的任意一个。
string指C++ STL中的std::string类。
有bug请及时私信我。
初始化： BigInteger A; A的值默认为0。
BigInteger A = BigInteger(); A的值默认为0。
BigInteger A(B); a的值为B。
BigInteger A = B; a的值为B。
赋值：
BigInteger A;
A = B; 把B的值赋给A。
取相反数：
-A A的相反数
小于号：
A < B 判断A是否小于B。
B < A 判断B是否小于A。
（>，<=，>=，==，!=同理）
类型转换（B可为bool，int，long long，string中的任意一个）：
显式：B = (B) A；
隐式：B = A;
C++流式输入输出：
cin >> A;
cout << A;
加法： A + B; A与B的和。
B + A; B与A的和。
A += B; 先把A加上B，再返回A的值。
（减法，乘法，除法，取模运算同理）
自减，自增操作：
A--; 先取值，后自减
--A; 先自减，后取值
A++; 先取值，后自增
++A; 先自增，后取值。
乘方 新： A.pow(B) A的B次方。
BigInteger模板：
#include <cassert>
#include <iostream>
#include <queue>
#include <deque>
#include <string>
#include <algorithm>
using namespace std;
struct BigInteger {
private:
deque<int> num;
bool sgn;
public:
BigInteger operator = (long long init) {
num.clear();
if (init) {
if (init > 0) sgn = true;
else {
sgn = false;
init = -init;
}
while (init) {
num.push_front(init % 10);
init /= 10;
}
} else {
sgn = true;
num.push_back(0);
}
return *this;
}
BigInteger operator = (int init) { return (*this = (long long) init); }
BigInteger operator = (const char *s) {
num.clear();
assert(*s);
if (*s == '-') {
sgn = false;
assert(*(++s));
} else sgn = true;
while (*s) {
assert(isdigit(*s));
num.push_back(*(s++) - '0');
}
if (num.size() >= 2) assert(num[0]);
assert(sgn || num[0]);
return *this;
}
BigInteger() { *this = 0LL; }
BigInteger(int init) { *this = init; }
BigInteger(long long init) { *this = init; }
BigInteger(const char *s) { *this = s; }
BigInteger(string s) { *this = s.c_str(); }
BigInteger operator - () {
if (num[0] == 0) return *this;
BigInteger ret = *this;
ret.sgn = !ret.sgn;
return ret;
}
bool operator < (const BigInteger &rhs) const {
if (sgn != rhs.sgn) return !sgn;
if (num.size() < rhs.num.size()) return sgn;
if (num.size() > rhs.num.size()) return !sgn;
for (int i = 0; i < num.size(); i++)
if (num[i] != rhs.num[i])
return (sgn ? (num[i] < rhs.num[i]) : (num[i] > rhs.num[i]));
return false;
}
bool operator < (int rhs) const { return *this < BigInteger(rhs); }
bool operator < (long long rhs) const { return *this < BigInteger(rhs); }
bool operator < (const char *rhs) const { return *this < BigInteger(rhs); }
bool operator < (string rhs) const { return *this < BigInteger(rhs); }
bool operator > (const BigInteger &rhs) const { return rhs < *this; }
bool operator > (int rhs) const { return *this > BigInteger(rhs); }
bool operator > (long long rhs) const { return *this > BigInteger(rhs); }
bool operator > (const char *rhs) const { return *this > BigInteger(rhs); }
bool operator > (string rhs) const { return *this > BigInteger(rhs); }
bool operator <= (const BigInteger &rhs) const { return !(*this > rhs); }
bool operator <= (int rhs) const { return *this <= BigInteger(rhs); }
bool operator <= (long long rhs) const { return *this <= BigInteger(rhs); }
bool operator <= (const char *rhs) const { return *this <= BigInteger(rhs); }
bool operator <= (string rhs) const { return *this <= BigInteger(rhs); }
bool operator >= (const BigInteger &rhs) const { return !(*this < rhs); }
bool operator >= (int rhs) const { return *this >= BigInteger(rhs); }
bool operator >= (long long rhs) const { return *this >= BigInteger(rhs); }
bool operator >= (const char *rhs) const { return *this >= BigInteger(rhs); }
bool operator >= (string rhs) const { return *this >= BigInteger(rhs); }
bool operator == (const BigInteger &rhs) const { return !(*this < rhs) && !(*this > rhs); }
bool operator == (int rhs) const { return *this == BigInteger(rhs); }
bool operator == (long long rhs) const { return *this == BigInteger(rhs); }
bool operator == (const char *rhs) const { return *this == BigInteger(rhs); }
bool operator == (string rhs) const { return *this == BigInteger(rhs); }
bool operator != (const BigInteger &rhs) const { return !(*this == rhs); }
bool operator != (int rhs) const { return *this != BigInteger(rhs); }
bool operator != (long long rhs) const { return *this != BigInteger(rhs); }
bool operator != (const char *rhs) const { return *this != BigInteger(rhs); }
bool operator != (string rhs) const { return *this != BigInteger(rhs); }
operator bool() {
return num[0];
}
operator string() {
string ret;
if (!sgn) ret += "-";
for (int i = 0; i < num.size(); i++) {
ret += num[i] + '0';
}
return ret;
}
operator int() {
int ret = 0;
for (int i = 0; i < num.size(); i++) ret = ret * 10 + num[i];
return ret;
}
operator long long() {
long long ret = 0;
for (int i = 0; i < num.size(); i++) ret = ret * 10 + num[i];
return ret;
}
friend istream& operator >> (istream &in, BigInteger &lhs) {
string init;
in >> init;
lhs = init;
return in;
}
friend ostream& operator << (ostream &out, BigInteger lhs) {
out << (string) lhs;
return out;
}
friend BigInteger operator + (BigInteger, BigInteger);
friend BigInteger operator - (BigInteger, BigInteger);
friend BigInteger operator * (BigInteger, BigInteger);
friend BigInteger operator / (BigInteger, BigInteger);
friend BigInteger operator % (BigInteger, BigInteger);
friend BigInteger operator + (BigInteger lhs, int rhs) { return lhs + BigInteger(rhs); }
friend BigInteger operator + (BigInteger lhs, long long rhs) { return lhs + BigInteger(rhs); }
friend BigInteger operator + (BigInteger lhs, const char *rhs) { return lhs + BigInteger(rhs); }
friend BigInteger operator + (BigInteger lhs, string rhs) { return lhs + BigInteger(rhs); }
friend BigInteger operator + (int lhs, BigInteger rhs) { return BigInteger(lhs) + rhs; }
friend BigInteger operator + (long long lhs, BigInteger rhs) { return BigInteger(lhs) + rhs; }
friend BigInteger operator + (const char *lhs, BigInteger rhs) { return BigInteger(lhs) + rhs; }
friend BigInteger operator + (string lhs, BigInteger rhs) { return BigInteger(lhs) + rhs; }
friend BigInteger operator - (BigInteger lhs, int rhs) { return lhs - BigInteger(rhs); }
friend BigInteger operator - (BigInteger lhs, long long rhs) { return lhs - BigInteger(rhs); }
friend BigInteger operator - (BigInteger lhs, const char *rhs) { return lhs - BigInteger(rhs); }
friend BigInteger operator - (BigInteger lhs, string rhs) { return lhs - BigInteger(rhs); }
friend BigInteger operator - (int lhs, BigInteger rhs) { return BigInteger(lhs) - rhs; }
friend BigInteger operator - (long long lhs, BigInteger rhs) { return BigInteger(lhs) - rhs; }
friend BigInteger operator - (const char *lhs, BigInteger rhs) { return BigInteger(lhs) - rhs; }
friend BigInteger operator - (string lhs, BigInteger rhs) { return BigInteger(lhs) - rhs; }
friend BigInteger operator * (BigInteger lhs, int rhs) { return lhs * BigInteger(rhs); }
friend BigInteger operator * (BigInteger lhs, long long rhs) { return lhs * BigInteger(rhs); }
friend BigInteger operator * (BigInteger lhs, const char *rhs) { return lhs * BigInteger(rhs); }
friend BigInteger operator * (BigInteger lhs, string rhs) { return lhs * BigInteger(rhs); }
friend BigInteger operator * (int lhs, BigInteger rhs) { return BigInteger(lhs) * rhs; }
friend BigInteger operator * (long long lhs, BigInteger rhs) { return BigInteger(lhs) * rhs; }
friend BigInteger operator * (const char *lhs, BigInteger rhs) { return BigInteger(lhs) * rhs; }
friend BigInteger operator * (string lhs, BigInteger rhs) { return BigInteger(lhs) * rhs; }
friend BigInteger operator / (BigInteger lhs, int rhs) { return lhs / BigInteger(rhs); }
friend BigInteger operator / (BigInteger lhs, long long rhs) { return lhs / BigInteger(rhs); }
friend BigInteger operator / (BigInteger lhs, const char *rhs) { return lhs / BigInteger(rhs); }
friend BigInteger operator / (BigInteger lhs, string rhs) { return lhs / BigInteger(rhs); }
friend BigInteger operator / (int lhs, BigInteger rhs) { return BigInteger(lhs) / rhs; }
friend BigInteger operator / (long long lhs, BigInteger rhs) { return BigInteger(lhs) / rhs; }
friend BigInteger operator / (const char *lhs, BigInteger rhs) { return BigInteger(lhs) / rhs; }
friend BigInteger operator / (string lhs, BigInteger rhs) { return BigInteger(lhs) / rhs; }
friend BigInteger operator % (BigInteger lhs, int rhs) { return lhs % BigInteger(rhs); }
friend BigInteger operator % (BigInteger lhs, long long rhs) { return lhs % BigInteger(rhs); }
friend BigInteger operator % (BigInteger lhs, const char *rhs) { return lhs % BigInteger(rhs); }
friend BigInteger operator % (BigInteger lhs, string rhs) { return lhs % BigInteger(rhs); }
friend BigInteger operator % (int lhs, BigInteger rhs) { return BigInteger(lhs) % rhs; }
friend BigInteger operator % (long long lhs, BigInteger rhs) { return BigInteger(lhs) % rhs; }
friend BigInteger operator % (const char *lhs, BigInteger rhs) { return BigInteger(lhs) % rhs; }
friend BigInteger operator % (string lhs, BigInteger rhs) { return BigInteger(lhs) % rhs; }
BigInteger & operator += (BigInteger rhs) {
*this = *this + rhs;
return *this;
}
BigInteger & operator += (int rhs) {
*this = *this + BigInteger(rhs);
return *this;
}
BigInteger & operator += (long long rhs) {
*this = *this + BigInteger(rhs);
return *this;
}
BigInteger & operator += (const char *rhs) {
*this = *this + BigInteger(rhs);
return *this;
}
BigInteger & operator += (string rhs) {
*this = *this + BigInteger(rhs);
return *this;
}
BigInteger & operator -= (BigInteger rhs) {
*this = *this - rhs;
return *this;
}
BigInteger & operator -= (int rhs) {
*this = *this - BigInteger(rhs);
return *this;
}
BigInteger & operator -= (long long rhs) {
*this = *this - BigInteger(rhs);
return *this;
}
BigInteger & operator -= (const char *rhs) {
*this = *this - BigInteger(rhs);
return *this;
}
BigInteger & operator -= (string rhs) {
*this = *this - BigInteger(rhs);
return *this;
}
BigInteger & operator *= (BigInteger rhs) {
*this = *this * BigInteger(rhs);
return *this;
}
BigInteger & operator *= (int rhs) {
*this = *this * BigInteger(rhs);
return *this;
}
BigInteger & operator *= (long long rhs) {
*this = *this * BigInteger(rhs);
return *this;
}
BigInteger & operator *= (const char *rhs) {
*this = *this * BigInteger(rhs);
return *this;
}
BigInteger & operator *= (string rhs) {
*this = *this * BigInteger(rhs);
return *this;
}
BigInteger & operator /= (BigInteger rhs) {
*this = *this / rhs;
return *this;
}
BigInteger & operator /= (int rhs) {
*this = *this / BigInteger(rhs);
return *this;
}
BigInteger & operator /= (long long rhs) {
*this = *this / BigInteger(rhs);
return *this;
}
BigInteger & operator /= (const char *rhs) {
*this = *this / BigInteger(rhs);
return *this;
}
BigInteger & operator /= (string rhs) {
*this = *this / BigInteger(rhs);
return *this;
}
BigInteger & operator %= (BigInteger rhs) {
*this = *this % BigInteger(rhs);
return *this;
}
BigInteger & operator %= (int rhs) {
*this = *this % BigInteger(rhs);
return *this;
}
BigInteger & operator %= (long long rhs) {
*this = *this % BigInteger(rhs);
return *this;
}
BigInteger & operator %= (const char *rhs) {
*this = *this % BigInteger(rhs);
return *this;
}
BigInteger & operator %= (string rhs) {
*this = *this % BigInteger(rhs);
return *this;
}
BigInteger & operator ++ () {
*this += BigInteger(1);
return *this;
}
BigInteger operator ++ (int _) {
BigInteger tmp(*this);
*this += BigInteger(1);
return tmp;
}
BigInteger & operator -- () {
*this -= BigInteger(1);
return *this;
}
BigInteger operator -- (int _) {
BigInteger tmp(*this);
*this -= BigInteger(1);
return tmp;
}
BigInteger pow(BigInteger n) {
assert(*this);
assert(n >= 0);
if (n == BigInteger(0)) return BigInteger(1);
BigInteger res = pow(n / BigInteger(2));
if (n % BigInteger(2)) return res * res * (*this);
return res * res;
}
BigInteger pow(int n) { return pow(BigInteger(n)); }
BigInteger pow(long long n) { return pow(BigInteger(n)); }
BigInteger pow(const char *n) { return pow(BigInteger(n)); }
BigInteger pow(string n) { return pow(BigInteger(n)); }
};
BigInteger operator + (BigInteger lhs, BigInteger rhs) {
if (lhs.sgn && !rhs.sgn) {
rhs.sgn = true;
return lhs - rhs;
}
if (!lhs.sgn && rhs.sgn) {
lhs.sgn = true;
return rhs - lhs;
}
if (lhs.num.size() < rhs.num.size()) swap(lhs, rhs);
for (int i = 0; i < rhs.num.size(); i++)
lhs.num[lhs.num.size() - rhs.num.size() + i] += rhs.num[i];
for (int i = lhs.num.size() - 1; i > 0; i--) {
lhs.num[i - 1] += lhs.num[i] / 10;
lhs.num[i] %= 10;
}
if (lhs.num[0] >= 10) {
lhs.num.push_front(lhs.num[0] / 10);
lhs.num[1] %= 10;
}
return lhs;
}
BigInteger operator - (BigInteger lhs, BigInteger rhs) {
if (lhs.sgn && !rhs.sgn) {
rhs.sgn = true;
return lhs + rhs;
}
if (!lhs.sgn && rhs.sgn) return lhs + rhs;
if (!lhs.sgn && !rhs.sgn) {
lhs.sgn = true;
rhs.sgn = true;
return rhs - lhs;
}
if (lhs < rhs) return -(rhs - lhs);
for (int i = lhs.num.size() - rhs.num.size(); i < lhs.num.size(); i++)
lhs.num[i] -= rhs.num[rhs.num.size() + i - lhs.num.size()];
for (int i = lhs.num.size() - 1; i > 0; i--) {
while (lhs.num[i] < 0) {
lhs.num[i - 1]--;
lhs.num[i] += 10;
}
}
while (lhs.num.size() >= 2 && lhs.num[0] == 0) lhs.num.pop_front();
return lhs;
}
BigInteger operator * (BigInteger lhs, BigInteger rhs) {
deque<int> mul(lhs.num.size() + rhs.num.size(), 0);
reverse(lhs.num.begin(), lhs.num.end());
reverse(rhs.num.begin(), rhs.num.end());
for (int i = 0; i < lhs.num.size(); i++)
for (int j = 0; j < rhs.num.size(); j++)
mul[i + j] += lhs.num[i] * rhs.num[j];
for (int i = 0; i < mul.size() - 1; i++) {
mul[i + 1] += mul[i] / 10;
mul[i] %= 10;
}
if (mul[mul.size() - 1]) {
mul.push_back(mul[mul.size() - 1] / 10);
mul[mul.size() - 2] %= 10;
}
while (mul.size() >= 2 && mul[mul.size() - 1] == 0) mul.pop_back();
reverse(mul.begin(), mul.end());
lhs.sgn = (lhs.sgn ^ rhs.sgn ^ 1);
lhs.num = mul;
return lhs;
}
BigInteger operator / (BigInteger lhs, BigInteger rhs) {
assert(rhs);
BigInteger ret, cnt, div;
bool sgn = (lhs.sgn ^ rhs.sgn ^ 1);
rhs.sgn = true;
div.num.clear();
for (int i = 0; i < lhs.num.size(); i++) {
while (!div.num.empty() && div.num[0] == 0) div.num.pop_front();
div.num.push_back(lhs.num[i]);
cnt = 0;
while (div > rhs) {
div -= rhs;
cnt++;
}
if (div == rhs) {
div = 0;
cnt++;
}
ret = ret * BigInteger(10) + cnt;
}
ret.sgn = sgn;
return ret;
}
BigInteger operator % (BigInteger lhs, BigInteger rhs) {
return lhs - lhs / rhs * rhs;
}
typedef BigInteger BigInt;
2022.3.18 (Ver 4)
新增除法，取模操作。优化代码结构。 从这个版本开始BigInteger大整数类基本上就没有什么新操作了。 有BUG请及时通知我（Qing_fy）。 Ver 4.2
#include <bits/stdc++.h>
using namespace std;
struct BigInteger {
private:
deque<int> num;
bool sgn;
public:
BigInteger operator = (long long init) {
num.clear();
if (init) {
if (init > 0) sgn = true;
else {
sgn = false;
init = -init;
}
while (init) {
num.push_front(init % 10);
init /= 10;
}
} else {
sgn = true;
num.push_back(0);
}
return *this;
}
BigInteger operator = (int init) { return (*this = (long long) init); }
BigInteger operator = (const char *s) {
num.clear();
assert(*s);
if (*s == '-') {
sgn = false;
assert(*(++s));
} else sgn = true;
while (*s) {
assert(isdigit(*s));
num.push_back(*(s++) - '0');
}
if (num.size() >= 2) assert(num[0]);
assert(sgn || num[0]);
return *this;
}
BigInteger() { *this = 0LL; }
BigInteger(int init) { *this = init; }
BigInteger(long long init) { *this = init; }
BigInteger(const char *s) { *this = s; }
BigInteger(string s) { *this = s.c_str(); }
BigInteger operator - () {
if (num[0] == 0) return *this;
BigInteger ret = *this;
ret.sgn = !ret.sgn;
return ret;
}
bool operator < (const BigInteger &rhs) const {
if (sgn != rhs.sgn) return !sgn;
if (num.size() < rhs.num.size()) return sgn;
if (num.size() > rhs.num.size()) return !sgn;
for (int i = 0; i < num.size(); i++)
if (num[i] != rhs.num[i])
return (sgn ? (num[i] < rhs.num[i]) : (num[i] > rhs.num[i]));
return false;
}
bool operator < (int rhs) const { return *this < BigInteger(rhs); }
bool operator < (long long rhs) const { return *this < BigInteger(rhs); }
bool operator < (const char *rhs) const { return *this < BigInteger(rhs); }
bool operator < (string rhs) const { return *this < BigInteger(rhs); }
bool operator > (const BigInteger &rhs) const { return rhs < *this; }
bool operator > (int rhs) const { return *this > BigInteger(rhs); }
bool operator > (long long rhs) const { return *this > BigInteger(rhs); }
bool operator > (const char *rhs) const { return *this > BigInteger(rhs); }
bool operator > (string rhs) const { return *this > BigInteger(rhs); }
bool operator <= (const BigInteger &rhs) const { return !(*this > rhs); }
bool operator <= (int rhs) const { return *this <= BigInteger(rhs); }
bool operator <= (long long rhs) const { return *this <= BigInteger(rhs); }
bool operator <= (const char *rhs) const { return *this <= BigInteger(rhs); }
bool operator <= (string rhs) const { return *this <= BigInteger(rhs); }
bool operator >= (const BigInteger &rhs) const { return !(*this < rhs); }
bool operator >= (int rhs) const { return *this >= BigInteger(rhs); }
bool operator >= (long long rhs) const { return *this >= BigInteger(rhs); }
bool operator >= (const char *rhs) const { return *this >= BigInteger(rhs); }
bool operator >= (string rhs) const { return *this >= BigInteger(rhs); }
bool operator == (const BigInteger &rhs) const { return !(*this < rhs) && !(*this > rhs); }
bool operator == (int rhs) const { return *this == BigInteger(rhs); }
bool operator == (long long rhs) const { return *this == BigInteger(rhs); }
bool operator == (const char *rhs) const { return *this == BigInteger(rhs); }
bool operator == (string rhs) const { return *this == BigInteger(rhs); }
bool operator != (const BigInteger &rhs) const { return !(*this == rhs); }
bool operator != (int rhs) const { return *this != BigInteger(rhs); }
bool operator != (long long rhs) const { return *this != BigInteger(rhs); }
bool operator != (const char *rhs) const { return *this != BigInteger(rhs); }
bool operator != (string rhs) const { return *this != BigInteger(rhs); }
operator bool() {
return num[0];
}
operator string() {
string ret;
if (!sgn) ret += "-";
for (int i = 0; i < num.size(); i++) {
ret += num[i] + '0';
}
return ret;
}
operator int() {
int ret = 0;
for (int i = 0; i < num.size(); i++) ret = ret * 10 + num[i];
return ret;
}
operator long long() {
long long ret = 0;
for (int i = 0; i < num.size(); i++) ret = ret * 10 + num[i];
return ret;
}
friend istream& operator >> (istream &in, BigInteger &lhs) {
string init;
in >> init;
lhs = init;
return in;
}
friend ostream& operator << (ostream &out, BigInteger lhs) {
out << (string) lhs;
return out;
}
friend BigInteger operator + (BigInteger, BigInteger);
friend BigInteger operator - (BigInteger, BigInteger);
friend BigInteger operator * (BigInteger, BigInteger);
friend BigInteger operator / (BigInteger, BigInteger);
friend BigInteger operator % (BigInteger, BigInteger);
friend BigInteger operator + (BigInteger lhs, int rhs) { return lhs + BigInteger(rhs); }
friend BigInteger operator + (BigInteger lhs, long long rhs) { return lhs + BigInteger(rhs); }
friend BigInteger operator + (BigInteger lhs, const char *rhs) { return lhs + BigInteger(rhs); }
friend BigInteger operator + (BigInteger lhs, string rhs) { return lhs + BigInteger(rhs); }
friend BigInteger operator + (int lhs, BigInteger rhs) { return BigInteger(lhs) + rhs; }
friend BigInteger operator + (long long lhs, BigInteger rhs) { return BigInteger(lhs) + rhs; }
friend BigInteger operator + (const char *lhs, BigInteger rhs) { return BigInteger(lhs) + rhs; }
friend BigInteger operator + (string lhs, BigInteger rhs) { return BigInteger(lhs) + rhs; }
friend BigInteger operator - (BigInteger lhs, int rhs) { return lhs - BigInteger(rhs); }
friend BigInteger operator - (BigInteger lhs, long long rhs) { return lhs - BigInteger(rhs); }
friend BigInteger operator - (BigInteger lhs, const char *rhs) { return lhs - BigInteger(rhs); }
friend BigInteger operator - (BigInteger lhs, string rhs) { return lhs - BigInteger(rhs); }
friend BigInteger operator - (int lhs, BigInteger rhs) { return BigInteger(lhs) - rhs; }
friend BigInteger operator - (long long lhs, BigInteger rhs) { return BigInteger(lhs) - rhs; }
friend BigInteger operator - (const char *lhs, BigInteger rhs) { return BigInteger(lhs) - rhs; }
friend BigInteger operator - (string lhs, BigInteger rhs) { return BigInteger(lhs) - rhs; }
friend BigInteger operator * (BigInteger lhs, int rhs) { return lhs * BigInteger(rhs); }
friend BigInteger operator * (BigInteger lhs, long long rhs) { return lhs * BigInteger(rhs); }
friend BigInteger operator * (BigInteger lhs, const char *rhs) { return lhs * BigInteger(rhs); }
friend BigInteger operator * (BigInteger lhs, string rhs) { return lhs * BigInteger(rhs); }
friend BigInteger operator * (int lhs, BigInteger rhs) { return BigInteger(lhs) * rhs; }
friend BigInteger operator * (long long lhs, BigInteger rhs) { return BigInteger(lhs) * rhs; }
friend BigInteger operator * (const char *lhs, BigInteger rhs) { return BigInteger(lhs) * rhs; }
friend BigInteger operator * (string lhs, BigInteger rhs) { return BigInteger(lhs) * rhs; }
friend BigInteger operator / (BigInteger lhs, int rhs) { return lhs / BigInteger(rhs); }
friend BigInteger operator / (BigInteger lhs, long long rhs) { return lhs / BigInteger(rhs); }
friend BigInteger operator / (BigInteger lhs, const char *rhs) { return lhs / BigInteger(rhs); }
friend BigInteger operator / (BigInteger lhs, string rhs) { return lhs / BigInteger(rhs); }
friend BigInteger operator / (int lhs, BigInteger rhs) { return BigInteger(lhs) / rhs; }
friend BigInteger operator / (long long lhs, BigInteger rhs) { return BigInteger(lhs) / rhs; }
friend BigInteger operator / (const char *lhs, BigInteger rhs) { return BigInteger(lhs) / rhs; }
friend BigInteger operator / (string lhs, BigInteger rhs) { return BigInteger(lhs) / rhs; }
friend BigInteger operator % (BigInteger lhs, int rhs) { return lhs % BigInteger(rhs); }
friend BigInteger operator % (BigInteger lhs, long long rhs) { return lhs % BigInteger(rhs); }
friend BigInteger operator % (BigInteger lhs, const char *rhs) { return lhs % BigInteger(rhs); }
friend BigInteger operator % (BigInteger lhs, string rhs) { return lhs % BigInteger(rhs); }
friend BigInteger operator % (int lhs, BigInteger rhs) { return BigInteger(lhs) % rhs; }
friend BigInteger operator % (long long lhs, BigInteger rhs) { return BigInteger(lhs) % rhs; }
friend BigInteger operator % (const char *lhs, BigInteger rhs) { return BigInteger(lhs) % rhs; }
friend BigInteger operator % (string lhs, BigInteger rhs) { return BigInteger(lhs) % rhs; }
BigInteger & operator += (BigInteger rhs) {
*this = *this + rhs;
return *this;
}
BigInteger & operator += (int rhs) {
*this = *this + BigInteger(rhs);
return *this;
}
BigInteger & operator += (long long rhs) {
*this = *this + BigInteger(rhs);
return *this;
}
BigInteger & operator += (const char *rhs) {
*this = *this + BigInteger(rhs);
return *this;
}
BigInteger & operator += (string rhs) {
*this = *this + BigInteger(rhs);
return *this;
}
BigInteger & operator -= (BigInteger rhs) {
*this = *this - rhs;
return *this;
}
BigInteger & operator -= (int rhs) {
*this = *this - BigInteger(rhs);
return *this;
}
BigInteger & operator -= (long long rhs) {
*this = *this - BigInteger(rhs);
return *this;
}
BigInteger & operator -= (const char *rhs) {
*this = *this - BigInteger(rhs);
return *this;
}
BigInteger & operator -= (string rhs) {
*this = *this - BigInteger(rhs);
return *this;
}
BigInteger & operator *= (BigInteger rhs) {
*this = *this * BigInteger(rhs);
return *this;
}
BigInteger & operator *= (int rhs) {
*this = *this * BigInteger(rhs);
return *this;
}
BigInteger & operator *= (long long rhs) {
*this = *this * BigInteger(rhs);
return *this;
}
BigInteger & operator *= (const char *rhs) {
*this = *this * BigInteger(rhs);
return *this;
}
BigInteger & operator *= (string rhs) {
*this = *this * BigInteger(rhs);
return *this;
}
BigInteger & operator /= (BigInteger rhs) {
*this = *this / rhs;
return *this;
}
BigInteger & operator /= (int rhs) {
*this = *this / BigInteger(rhs);
return *this;
}
BigInteger & operator /= (long long rhs) {
*this = *this / BigInteger(rhs);
return *this;
}
BigInteger & operator /= (const char *rhs) {
*this = *this / BigInteger(rhs);
return *this;
}
BigInteger & operator /= (string rhs) {
*this = *this / BigInteger(rhs);
return *this;
}
BigInteger & operator %= (BigInteger rhs) {
*this = *this % BigInteger(rhs);
return *this;
}
BigInteger & operator %= (int rhs) {
*this = *this % BigInteger(rhs);
return *this;
}
BigInteger & operator %= (long long rhs) {
*this = *this % BigInteger(rhs);
return *this;
}
BigInteger & operator %= (const char *rhs) {
*this = *this % BigInteger(rhs);
return *this;
}
BigInteger & operator %= (string rhs) {
*this = *this % BigInteger(rhs);
return *this;
}
BigInteger & operator ++ () {
*this += BigInteger(1);
return *this;
}
BigInteger operator ++ (int _) {
BigInteger tmp(*this);
*this += BigInteger(1);
return tmp;
}
BigInteger & operator -- () {
*this -= BigInteger(1);
return *this;
}
BigInteger operator -- (int _) {
BigInteger tmp(*this);
*this -= BigInteger(1);
return *this;
}
};
BigInteger operator + (BigInteger lhs, BigInteger rhs) {
if (lhs.sgn && !rhs.sgn) {
rhs.sgn = true;
return lhs - rhs;
}
if (!lhs.sgn && rhs.sgn) {
lhs.sgn = true;
return rhs - lhs;
}
if (lhs.num.size() < rhs.num.size()) swap(lhs, rhs);
for (int i = 0; i < rhs.num.size(); i++)
lhs.num[lhs.num.size() - rhs.num.size() + i] += rhs.num[i];
for (int i = lhs.num.size() - 1; i > 0; i--) {
lhs.num[i - 1] += lhs.num[i] / 10;
lhs.num[i] %= 10;
}
if (lhs.num[0] >= 10) {
lhs.num.push_front(lhs.num[0] / 10);
lhs.num[1] %= 10;
}
return lhs;
}
BigInteger operator - (BigInteger lhs, BigInteger rhs) {
if (lhs.sgn && !rhs.sgn) {
rhs.sgn = true;
return lhs + rhs;
}
if (!lhs.sgn && rhs.sgn) return lhs + rhs;
if (!lhs.sgn && !rhs.sgn) {
lhs.sgn = true;
rhs.sgn = true;
return rhs - lhs;
}
if (lhs < rhs) return -(rhs - lhs);
for (int i = lhs.num.size() - rhs.num.size(); i < lhs.num.size(); i++)
lhs.num[i] -= rhs.num[rhs.num.size() + i - lhs.num.size()];
for (int i = lhs.num.size() - 1; i > 0; i--) {
while (lhs.num[i] < 0) {
lhs.num[i - 1]--;
lhs.num[i] += 10;
}
}
while (lhs.num.size() >= 2 && lhs.num[0] == 0) lhs.num.pop_front();
return lhs;
}
BigInteger operator * (BigInteger lhs, BigInteger rhs) {
deque<int> mul(lhs.num.size() + rhs.num.size(), 0);
reverse(lhs.num.begin(), lhs.num.end());
reverse(rhs.num.begin(), rhs.num.end());
for (int i = 0; i < lhs.num.size(); i++)
for (int j = 0; j < rhs.num.size(); j++)
mul[i + j] += lhs.num[i] * rhs.num[j];
for (int i = 0; i < mul.size() - 1; i++) {
mul[i + 1] += mul[i] / 10;
mul[i] %= 10;
}
if (mul[mul.size() - 1]) {
mul.push_back(mul[mul.size() - 1] / 10);
mul[mul.size() - 2] %= 10;
}
while (mul.size() >= 2 && mul[mul.size() - 1] == 0) mul.pop_back();
reverse(mul.begin(), mul.end());
lhs.sgn = (lhs.sgn ^ rhs.sgn ^ 1);
lhs.num = mul;
return lhs;
}
BigInteger operator / (BigInteger lhs, BigInteger rhs) {
assert(rhs);
BigInteger ret, cnt, div;
bool sgn = (lhs.sgn ^ rhs.sgn ^ 1);
rhs.sgn = true;
div.num.clear();
for (int i = 0; i < lhs.num.size(); i++) {
while (!div.num.empty() && div.num[0] == 0) div.num.pop_front();
div.num.push_back(lhs.num[i]);
cnt = 0;
while (div > rhs) {
div -= rhs;
cnt++;
}
if (div == rhs) {
div = 0;
cnt++;
}
ret = ret * BigInteger(10) + cnt;
}
ret.sgn = sgn;
return ret;
}
BigInteger operator % (BigInteger lhs, BigInteger rhs) {
return lhs - lhs / rhs * rhs;
}
typedef BigInteger BigInt;
int main() {
// YOUR CODE HERE.
return 0;
}Ver4.1
#include <bits/stdc++.h>
using namespace std;
struct BigInteger {
private:
deque<int> num;
bool sgn;
public:
BigInteger operator = (long long init) {
num.clear();
if (init) {
if (init > 0) sgn = true;
else {
sgn = false;
init = -init;
}
while (init) {
num.push_front(init % 10);
init /= 10;
}
} else {
sgn = true;
num.push_back(0);
}
return *this;
}
BigInteger operator = (int init) { return (*this = (long long) init); }
BigInteger operator = (const char *s) {
num.clear();
assert(*s);
if (*s == '-') {
sgn = false;
assert(*(++s));
} else sgn = true;
while (*s) {
assert(isdigit(*s));
num.push_back(*(s++) - '0');
}
if (num.size() >= 2) assert(num[0]);
assert(sgn || num[0]);
return *this;
}
BigInteger() { *this = 0LL; }
BigInteger(int init) { *this = init; }
BigInteger(long long init) { *this = init; }
BigInteger(const char *s) { *this = s; }
BigInteger(string s) { *this = s.c_str(); }
BigInteger operator - () {
if (num[0] == 0) return *this;
BigInteger ret = *this;
ret.sgn = !ret.sgn;
return ret;
}
bool operator < (const BigInteger &rhs) const {
if (sgn != rhs.sgn) return !sgn;
if (num.size() < rhs.num.size()) return sgn;
if (num.size() > rhs.num.size()) return !sgn;
for (int i = 0; i < num.size(); i++)
if (num[i] != rhs.num[i])
return (sgn ? (num[i] < rhs.num[i]) : (num[i] > rhs.num[i]));
return false;
}
bool operator > (const BigInteger &rhs) const { return rhs < *this; }
bool operator <= (const BigInteger &rhs) const { return !(*this > rhs); }
bool operator >= (const BigInteger &rhs) const { return !(*this < rhs); }
bool operator == (const BigInteger &rhs) const { return !(*this < rhs) && !(*this > rhs); }
bool operator != (const BigInteger &rhs) const { return !(*this == rhs); }
operator bool() {
return num[0];
}
operator string() {
string ret;
if (!sgn) ret += "-";
for (int i = 0; i < num.size(); i++) {
ret += num[i] + '0';
}
return ret;
}
operator int() {
int ret = 0;
for (int i = 0; i < num.size(); i++) ret = ret * 10 + num[i];
return ret;
}
operator long long() {
long long ret = 0;
for (int i = 0; i < num.size(); i++) ret = ret * 10 + num[i];
return ret;
}
friend istream& operator >> (istream &in, BigInteger &lhs) {
string init;
in >> init;
lhs = init;
return in;
}
friend ostream& operator << (ostream &out, BigInteger lhs) {
out << (string) lhs;
return out;
}
friend BigInteger operator + (BigInteger, BigInteger);
friend BigInteger operator - (BigInteger, BigInteger);
friend BigInteger operator * (BigInteger, BigInteger);
friend BigInteger operator / (BigInteger, BigInteger);
friend BigInteger operator % (BigInteger, BigInteger);
BigInteger & operator += (BigInteger rhs) {
*this = *this + rhs;
return *this;
}
BigInteger & operator -= (BigInteger rhs) {
*this = *this - rhs;
return *this;
}
BigInteger & operator *= (BigInteger rhs) {
*this = *this * rhs;
return *this;
}
BigInteger & operator /= (BigInteger rhs) {
*this = *this / rhs;
return *this;
}
BigInteger & operator %= (BigInteger rhs) {
*this = *this % rhs;
return *this;
}
BigInteger & operator ++ () {
*this += BigInteger(1);
return *this;
}
BigInteger operator ++ (int _) {
BigInteger tmp(*this);
*this += BigInteger(1);
return tmp;
}
BigInteger & operator -- () {
*this -= BigInteger(1);
return *this;
}
BigInteger operator -- (int _) {
BigInteger tmp(*this);
*this -= BigInteger(1);
return *this;
}
};
BigInteger operator + (BigInteger lhs, BigInteger rhs) {
if (lhs.sgn && !rhs.sgn) {
rhs.sgn = true;
return lhs - rhs;
}
if (!lhs.sgn && rhs.sgn) {
lhs.sgn = true;
return rhs - lhs;
}
if (lhs.num.size() < rhs.num.size()) swap(lhs, rhs);
for (int i = 0; i < rhs.num.size(); i++)
lhs.num[lhs.num.size() - rhs.num.size() + i] += rhs.num[i];
for (int i = lhs.num.size() - 1; i > 0; i--) {
lhs.num[i - 1] += lhs.num[i] / 10;
lhs.num[i] %= 10;
}
if (lhs.num[0] >= 10) {
lhs.num.push_front(lhs.num[0] / 10);
lhs.num[1] %= 10;
}
return lhs;
}
BigInteger operator - (BigInteger lhs, BigInteger rhs) {
if (lhs.sgn && !rhs.sgn) {
rhs.sgn = true;
return lhs + rhs;
}
if (!lhs.sgn && rhs.sgn) return lhs + rhs;
if (!lhs.sgn && !rhs.sgn) {
lhs.sgn = true;
rhs.sgn = true;
return rhs - lhs;
}
if (lhs < rhs) return -(rhs - lhs);
for (int i = lhs.num.size() - rhs.num.size(); i < lhs.num.size(); i++)
lhs.num[i] -= rhs.num[rhs.num.size() + i - lhs.num.size()];
for (int i = lhs.num.size() - 1; i > 0; i--) {
while (lhs.num[i] < 0) {
lhs.num[i - 1]--;
lhs.num[i] += 10;
}
}
while (lhs.num.size() >= 2 && lhs.num[0] == 0) lhs.num.pop_front();
return lhs;
}
BigInteger operator * (BigInteger lhs, BigInteger rhs) {
deque<int> mul(lhs.num.size() + rhs.num.size(), 0);
reverse(lhs.num.begin(), lhs.num.end());
reverse(rhs.num.begin(), rhs.num.end());
for (int i = 0; i < lhs.num.size(); i++)
for (int j = 0; j < rhs.num.size(); j++)
mul[i + j] += lhs.num[i] * rhs.num[j];
for (int i = 0; i < mul.size() - 1; i++) {
mul[i + 1] += mul[i] / 10;
mul[i] %= 10;
}
if (mul[mul.size() - 1]) {
mul.push_back(mul[mul.size() - 1] / 10);
mul[mul.size() - 2] %= 10;
}
while (mul.size() >= 2 && mul[mul.size() - 1] == 0) mul.pop_back();
reverse(mul.begin(), mul.end());
lhs.sgn = (lhs.sgn ^ rhs.sgn ^ 1);
lhs.num = mul;
return lhs;
}
BigInteger operator / (BigInteger lhs, BigInteger rhs) {
assert(rhs);
BigInteger ret, cnt, div;
bool sgn = (lhs.sgn ^ rhs.sgn ^ 1);
rhs.sgn = true;
div.num.clear();
for (int i = 0; i < lhs.num.size(); i++) {
while (!div.num.empty() && div.num[0] == 0) div.num.pop_front();
div.num.push_back(lhs.num[i]);
cnt = 0;
while (div > rhs) {
div -= rhs;
cnt++;
}
if (div == rhs) {
div = 0;
cnt++;
}
ret = ret * BigInteger(10) + cnt;
}
ret.sgn = sgn;
return ret;
}
BigInteger operator % (BigInteger lhs, BigInteger rhs) {
return lhs - lhs / rhs * rhs;
}
typedef BigInteger BigInt;
int main() {
// YOUR CODE HERE.
return 0;
}2022.3.17 (Ver 3)
新增乘法操作。定义BigInteger的别名BigInt Ver3.2：修复cout输出的bug，优化代码结构，增加自增自减操作，声明除法操作。
#include <bits/stdc++.h>
using namespace std;
struct BigInteger {
private:
deque<int> num; // Digital part
bool sgn; // Plus or minus sign
public:
// Copy with a variable of type long long int.
BigInteger operator = (long long init) {
num.clear();
if (init) {
if (init > 0) sgn = true;
else {
sgn = false;
init = -init;
}
while (init) {
num.push_front(init % 10);
init /= 10;
}
} else {
sgn = true;
num.push_back(0);
}
return *this;
}
// Copy with a variable of type int.
BigInteger operator = (int init) { return (*this = (long long) init); }
// Copy with a variable of type 'C string'.
BigInteger operator = (const char *s) {
num.clear();
assert(*s);
if (*s == '-') {
sgn = false;
assert(*(++s));
} else sgn = true;
while (*s) {
assert(isdigit(*s));
num.push_back(*(s++) - '0');
}
if (num.size() >= 2) assert(num[0]);
assert(sgn || num[0]);
return *this;
}
BigInteger() { *this = 0LL; } // Initialize with nothing. The value of object will become zero;
BigInteger(int init) { *this = init; } // Initialize with a variable of type int.
BigInteger(long long init) { *this = init; } // Initialize with a variable of type long long int.
BigInteger(const char *s) { *this = s; } // Initialize with a variable of type 'C string'.
BigInteger(string s) { *this = s.c_str(); } // // Initialize with a variable of 'C++ string'.
// Negative operation
BigInteger operator - () {
if (num[0] == 0) return *this;
BigInteger ret = *this;
ret.sgn = !ret.sgn;
return ret;
}
// Less than (operation <)
bool operator < (const BigInteger &rhs) const {
if (sgn != rhs.sgn) return !sgn;
if (num.size() < rhs.num.size()) return sgn;
if (num.size() > rhs.num.size()) return !sgn;
for (int i = 0; i < num.size(); i++)
if (num[i] != rhs.num[i])
return (sgn ? (num[i] < rhs.num[i]) : (num[i] > rhs.num[i]));
return false;
}
// others rely operation <
bool operator > (const BigInteger &rhs) const { return rhs < *this; }
bool operator <= (const BigInteger &rhs) const { return !(*this > rhs); }
bool operator >= (const BigInteger &rhs) const { return !(*this < rhs); }
bool operator == (const BigInteger &rhs) const { return !(*this < rhs) && !(*this > rhs); }
bool operator != (const BigInteger &rhs) const { return !(*this == rhs); }
// Convert to bool type
operator bool() {
return num[0];
}
// Convert to 'C++ string' type
operator string() {
string ret;
if (!sgn) ret += "-";
for (int i = 0; i < num.size(); i++) {
ret += num[i] + '0';
}
return ret;
}
// Convert to int type
operator int() {
int ret = 0;
for (int i = 0; i < num.size(); i++) ret = ret * 10 + num[i];
return ret;
}
// Convert to long long int type
operator long long() {
long long ret = 0;
for (int i = 0; i < num.size(); i++) ret = ret * 10 + num[i];
return ret;
}
// Make the type support cin.
friend istream& operator >> (istream &in, BigInteger &lhs) {
string init;
in >> init;
lhs = init;
return in;
}
// Make the type support cout.
friend ostream& operator << (ostream &out, BigInteger lhs) {
out << (string) lhs;
return out;
}
// Declaring the Four Arithmetic.
friend BigInteger operator + (BigInteger, BigInteger);
friend BigInteger operator - (BigInteger, BigInteger);
friend BigInteger operator * (BigInteger, BigInteger);
friend BigInteger operator / (BigInteger, BigInteger);
friend BigInteger operator % (BigInteger, BigInteger); // Modulo operation
// Equal to '*this = *this + rhs'.
BigInteger & operator += (BigInteger rhs) {
*this = *this + rhs;
return *this;
}
// Equal to '*this = *this - rhs'.
BigInteger & operator -= (BigInteger rhs) {
*this = *this - rhs;
return *this;
}
// Equal to '*this = *this * rhs'.
BigInteger & operator *= (BigInteger rhs) {
*this = *this * rhs;
return *this;
}
// Pre-increment
BigInteger & operator ++ () {
*this += BigInteger(1);
return *this;
}
// Post-increment
BigInteger operator ++ (int _) {
BigInteger tmp(*this);
*this += BigInteger(1);
return tmp;
}
// Pre-decrement
BigInteger & operator -- () {
*this -= BigInteger(1);
return *this;
}
// Post-decrement
BigInteger operator -- (int _) {
BigInteger tmp(*this);
*this -= BigInteger(1);
return *this;
}
};
// Four arithmetic operations
BigInteger operator + (BigInteger lhs, BigInteger rhs) {
if (lhs.sgn && !rhs.sgn) {
rhs.sgn = true;
return lhs - rhs;
}
if (!lhs.sgn && rhs.sgn) {
lhs.sgn = true;
return rhs - lhs;
}
if (lhs.num.size() < rhs.num.size()) swap(lhs, rhs);
for (int i = 0; i < rhs.num.size(); i++)
lhs.num[lhs.num.size() - rhs.num.size() + i] += rhs.num[i];
for (int i = lhs.num.size() - 1; i > 0; i--) {
lhs.num[i - 1] += lhs.num[i] / 10;
lhs.num[i] %= 10;
}
if (lhs.num[0] >= 10) {
lhs.num.push_front(lhs.num[0] / 10);
lhs.num[1] %= 10;
}
return lhs;
}
BigInteger operator - (BigInteger lhs, BigInteger rhs) {
if (lhs.sgn && !rhs.sgn) {
rhs.sgn = true;
return lhs + rhs;
}
if (!lhs.sgn && rhs.sgn) return lhs + rhs;
if (!lhs.sgn && !rhs.sgn) {
lhs.sgn = true;
rhs.sgn = true;
return rhs - lhs;
}
if (lhs < rhs) return -(rhs - lhs);
for (int i = lhs.num.size() - rhs.num.size(); i < lhs.num.size(); i++)
lhs.num[i] -= rhs.num[rhs.num.size() + i - lhs.num.size()];
for (int i = lhs.num.size() - 1; i > 0; i--) {
while (lhs.num[i] < 0) {
lhs.num[i - 1]--;
lhs.num[i] += 10;
}
}
while (lhs.num.size() >= 2 && lhs.num[0] == 0) lhs.num.pop_front();
return lhs;
}
BigInteger operator * (BigInteger lhs, BigInteger rhs) {
deque<int> mul(lhs.num.size() + rhs.num.size(), 0);
reverse(lhs.num.begin(), lhs.num.end());
reverse(rhs.num.begin(), rhs.num.end());
for (int i = 0; i < lhs.num.size(); i++)
for (int j = 0; j < rhs.num.size(); j++)
mul[i + j] += lhs.num[i] * rhs.num[j];
for (int i = 0; i < mul.size() - 1; i++) {
mul[i + 1] += mul[i] / 10;
mul[i] %= 10;
}
if (mul[mul.size() - 1]) {
mul.push_back(mul[mul.size() - 1] / 10);
mul[mul.size() - 2] %= 10;
}
while (mul.size() >= 2 && mul[mul.size() - 1] == 0) mul.pop_back();
reverse(mul.begin(), mul.end());
lhs.sgn = (lhs.sgn ^ rhs.sgn ^ 1);
lhs.num = mul;
return lhs;
}
BigInteger operator / (BigInteger lhs, BigInteger rhs) {
abort();
}
typedef BigInteger BigInt;
int main() {
// YOUR CODE HERE.
return 0;
}Ver3.1：紧急修复乘法运算的bug。
#include <bits/stdc++.h>
using namespace std;
struct BigInteger {
private:
deque<int> num;
bool sgn;
public:
BigInteger operator = (long long init) {
num.clear();
if (init) {
if (init > 0) sgn = true;
else {
sgn = false;
init = -init;
}
while (init) {
num.push_front(init % 10);
init /= 10;
}
} else {
sgn = true;
num.push_back(0);
}
return *this;
}
BigInteger operator = (int init) { return (*this = (long long) init); }
BigInteger operator = (const char* s) {
num.clear();
assert(*s);
if (*s == '-') {
sgn = false;
assert(*(++s));
} else sgn = true;
while (*s) {
assert(isdigit(*s));
num.push_back(*(s++) - '0');
}
if (num.size() >= 2) assert(num[0]);
assert(sgn || num[0]);
return *this;
}
BigInteger() { *this = 0LL; }
BigInteger(int init) { *this = init; }
BigInteger(long long init) { *this = init; }
BigInteger(const char* s) { *this = s; }
BigInteger(string s) { *this = s.c_str(); }
BigInteger operator - () {
if (num[0] == 0) return *this;
BigInteger ret = *this;
ret.sgn = !ret.sgn;
return ret;
}
bool operator < (const BigInteger &rhs) const {
if (sgn != rhs.sgn) return !sgn;
if (num.size() < rhs.num.size()) return sgn;
if (num.size() > rhs.num.size()) return !sgn;
for (int i = 0; i < num.size(); i++)
if (num[i] != rhs.num[i])
return (sgn ? (num[i] < rhs.num[i]) : (num[i] > rhs.num[i]));
return false;
}
bool operator > (const BigInteger &rhs) const { return rhs < *this; }
bool operator <= (const BigInteger &rhs) const { return !(*this > rhs); }
bool operator >= (const BigInteger &rhs) const { return !(*this < rhs); }
bool operator == (const BigInteger &rhs) const { return !(*this < rhs) && !(*this > rhs); }
bool operator != (const BigInteger &rhs) const { return !(*this == rhs); }
operator bool() {
return num[0];
}
operator string() {
string ret;
if (!sgn) ret += "-";
for (int i = 0; i < num.size(); i++) {
ret += num[i] + '0';
}
return ret;
}
operator int() {
int ret = 0;
for (int i = 0; i < num.size(); i++) ret = ret * 10 + num[i];
return ret;
}
operator long long() {
long long ret = 0;
for (int i = 0; i < num.size(); i++) ret = ret * 10 + num[i];
return ret;
}
friend istream& operator >> (istream& in, BigInteger &lhs) {
string init;
in >> init;
lhs = init;
return in;
}
friend ostream& operator << (ostream& out, BigInteger lhs) {
out << (string) lhs;
return out;
}
friend BigInteger operator + (BigInteger, BigInteger);
friend BigInteger operator - (BigInteger, BigInteger);
friend BigInteger operator * (BigInteger, BigInteger);
};
BigInteger operator + (BigInteger lhs, BigInteger rhs) {
if (lhs.sgn && !rhs.sgn) {
rhs.sgn = true;
return lhs - rhs;
}
if (!lhs.sgn && rhs.sgn) {
lhs.sgn = true;
return rhs - lhs;
}
if (lhs.num.size() < rhs.num.size()) swap(lhs, rhs);
for (int i = 0; i < rhs.num.size(); i++)
lhs.num[lhs.num.size() - rhs.num.size() + i] += rhs.num[i];
for (int i = lhs.num.size() - 1; i > 0; i--) {
lhs.num[i - 1] += lhs.num[i] / 10;
lhs.num[i] %= 10;
}
if (lhs.num[0] >= 10) {
lhs.num.push_front(lhs.num[0] / 10);
lhs.num[1] %= 10;
}
return lhs;
}
BigInteger operator - (BigInteger lhs, BigInteger rhs) {
if (lhs.sgn && !rhs.sgn) {
rhs.sgn = true;
return lhs + rhs;
}
if (!lhs.sgn && rhs.sgn) return lhs + rhs;
if (!lhs.sgn && !rhs.sgn) {
lhs.sgn = true;
rhs.sgn = true;
return rhs - lhs;
}
if (lhs < rhs) return -(rhs - lhs);
for (int i = lhs.num.size() - rhs.num.size(); i < lhs.num.size(); i++)
lhs.num[i] -= rhs.num[rhs.num.size() + i - lhs.num.size()];
for (int i = lhs.num.size() - 1; i > 0; i--) {
while (lhs.num[i] < 0) {
lhs.num[i - 1]--;
lhs.num[i] += 10;
}
}
while (lhs.num.size() >= 2 && lhs.num[0] == 0) lhs.num.pop_front();
return lhs;
}
BigInteger operator * (BigInteger lhs, BigInteger rhs) {
deque<int> mul(lhs.num.size() + rhs.num.size(), 0);
reverse(lhs.num.begin(), lhs.num.end());
reverse(rhs.num.begin(), rhs.num.end());
for (int i = 0; i < lhs.num.size(); i++)
for (int j = 0; j < rhs.num.size(); j++)
mul[i + j] += lhs.num[i] * rhs.num[j];
for (int i = 0; i < mul.size() - 1; i++) {
mul[i + 1] += mul[i] / 10;
mul[i] %= 10;
}
if (mul[mul.size() - 1]) {
mul.push_back(mul[mul.size() - 1] / 10);
mul[mul.size() - 2] %= 10;
}
while (mul.size() >= 2 && mul[mul.size() - 1] == 0) mul.pop_back();
reverse(mul.begin(), mul.end());
lhs.sgn = (lhs.sgn ^ rhs.sgn ^ 1);
lhs.num = mul;
return lhs;
}
typedef BigInteger BigInt;
int main() {
// YOUR CODE HERE.
return 0;
}Ver3.0
#include <bits/stdc++.h>
using namespace std;
struct BigInteger {
private:
deque<int> num;
bool sgn;
public:
BigInteger operator = (long long init) {
num.clear();
if (init) {
if (init > 0) sgn = true;
else {
sgn = false;
init = -init;
}
while (init) {
num.push_front(init % 10);
init /= 10;
}
} else {
sgn = true;
num.push_back(0);
}
return *this;
}
BigInteger operator = (int init) { return (*this = (long long) init); }
BigInteger operator = (const char* s) {
num.clear();
assert(*s);
if (*s == '-') {
sgn = false;
assert(*(++s));
} else sgn = true;
while (*s) {
assert(isdigit(*s));
num.push_back(*(s++) - '0');
}
if (num.size() >= 2) assert(num[0]);
assert(sgn || num[0]);
return *this;
}
BigInteger() { *this = 0LL; }
BigInteger(int init) { *this = init; }
BigInteger(long long init) { *this = init; }
BigInteger(const char* s) { *this = s; }
BigInteger(string s) { *this = s.c_str(); }
BigInteger operator - () {
if (num[0] == 0) return *this;
BigInteger ret = *this;
ret.sgn = !ret.sgn;
return ret;
}
bool operator < (const BigInteger &rhs) const {
if (sgn != rhs.sgn) return !sgn;
if (num.size() < rhs.num.size()) return sgn;
if (num.size() > rhs.num.size()) return !sgn;
for (int i = 0; i < num.size(); i++)
if (num[i] != rhs.num[i])
return (sgn ? (num[i] < rhs.num[i]) : (num[i] > rhs.num[i]));
return false;
}
bool operator > (const BigInteger &rhs) const { return rhs < *this; }
bool operator <= (const BigInteger &rhs) const { return !(*this > rhs); }
bool operator >= (const BigInteger &rhs) const { return !(*this < rhs); }
bool operator == (const BigInteger &rhs) const { return !(*this < rhs) && !(*this > rhs); }
bool operator != (const BigInteger &rhs) const { return !(*this == rhs); }
operator bool() {
return num[0];
}
operator string() {
string ret;
if (!sgn) ret += "-";
for (int i = 0; i < num.size(); i++) {
ret += num[i] + '0';
}
return ret;
}
operator int() {
int ret = 0;
for (int i = 0; i < num.size(); i++) ret = ret * 10 + num[i];
return ret;
}
operator long long() {
long long ret = 0;
for (int i = 0; i < num.size(); i++) ret = ret * 10 + num[i];
return ret;
}
friend istream& operator >> (istream& in, BigInteger &lhs) {
string init;
in >> init;
lhs = init;
return in;
}
friend ostream& operator << (ostream& out, BigInteger lhs) {
out << (string) lhs;
return out;
}
friend BigInteger operator + (BigInteger, BigInteger);
friend BigInteger operator - (BigInteger, BigInteger);
friend BigInteger operator * (BigInteger, BigInteger);
};
BigInteger operator + (BigInteger lhs, BigInteger rhs) {
if (lhs.sgn && !rhs.sgn) {
rhs.sgn = true;
return lhs - rhs;
}
if (!lhs.sgn && rhs.sgn) {
lhs.sgn = true;
return rhs - lhs;
}
if (lhs.num.size() < rhs.num.size()) swap(lhs, rhs);
for (int i = 0; i < rhs.num.size(); i++)
lhs.num[lhs.num.size() - rhs.num.size() + i] += rhs.num[i];
for (int i = lhs.num.size() - 1; i > 0; i--) {
lhs.num[i - 1] += lhs.num[i] / 10;
lhs.num[i] %= 10;
}
if (lhs.num[0] >= 10) {
lhs.num.push_front(lhs.num[0] / 10);
lhs.num[1] %= 10;
}
return lhs;
}
BigInteger operator - (BigInteger lhs, BigInteger rhs) {
if (lhs.sgn && !rhs.sgn) {
rhs.sgn = true;
return lhs + rhs;
}
if (!lhs.sgn && rhs.sgn) return lhs + rhs;
if (!lhs.sgn && !rhs.sgn) {
lhs.sgn = true;
rhs.sgn = true;
return rhs - lhs;
}
if (lhs < rhs) return -(rhs - lhs);
for (int i = lhs.num.size() - rhs.num.size(); i < lhs.num.size(); i++)
lhs.num[i] -= rhs.num[rhs.num.size() + i - lhs.num.size()];
for (int i = lhs.num.size() - 1; i > 0; i--) {
while (lhs.num[i] < 0) {
lhs.num[i - 1]--;
lhs.num[i] += 10;
}
}
while (lhs.num.size() >= 2 && lhs.num[0] == 0) lhs.num.pop_front();
return lhs;
}
BigInteger operator * (BigInteger lhs, BigInteger rhs) {
deque<int> mul(lhs.num.size() + rhs.num.size(), 0);
reverse(lhs.num.begin(), lhs.num.end());
reverse(rhs.num.begin(), rhs.num.end());
for (int i = 0; i < lhs.num.size(); i++)
for (int j = 0; j < rhs.num.size(); j++)
mul[i + j] += lhs.num[i] * rhs.num[j];
for (int i = 0; i < mul.size() - 1; i++) {
mul[i + 1] += mul[i] / 10;
mul[i] %= 10;
}
if (mul[mul.size() - 1]) {
mul.push_front(mul[mul.size() - 1] / 10);
mul[mul.size() - 2] %= 10;
}
reverse(mul.begin(), mul.end());
while (mul.size() >= 2 && mul[0] == 0) mul.pop_front();
lhs.sgn = (lhs.sgn ^ rhs.sgn ^ 1);
lhs.num = mul;
return lhs;
}
typedef BigInteger BigInt;
int main() {
// YOUR CODE HERE.
return 0;
}2022.3.17 (Ver 2)
完善加法操作。添加减法操作（所有）。 Ver2.1
#include <bits/stdc++.h>
using namespace std;
struct BigInteger {
private:
deque<int> num;
bool sgn;
public:
BigInteger operator = (long long init) {
num.clear();
if (init) {
if (init > 0) sgn = true;
else {
sgn = false;
init = -init;
}
while (init) {
num.push_front(init % 10);
init /= 10;
}
} else {
sgn = true;
num.push_back(0);
}
return *this;
}
BigInteger operator = (int init) { return (*this = (long long) init); }
BigInteger operator = (const char* s) {
num.clear();
assert(*s);
if (*s == '-') {
sgn = false;
assert(*(++s));
} else sgn = true;
while (*s) {
assert(isdigit(*s));
num.push_back(*(s++) - '0');
}
if (num.size() >= 2) assert(num[0]);
assert(sgn || num[0]);
return *this;
}
BigInteger() { *this = 0LL; }
BigInteger(int init) { *this = init; }
BigInteger(long long init) { *this = init; }
BigInteger(const char* s) { *this = s; }
BigInteger(string s) { *this = s.c_str(); }
BigInteger operator - () {
if (num[0] == 0) return *this;
BigInteger ret = *this;
ret.sgn = !ret.sgn;
return ret;
}
bool operator < (const BigInteger &rhs) const {
if (sgn != rhs.sgn) return !sgn;
if (num.size() < rhs.num.size()) return sgn;
if (num.size() > rhs.num.size()) return !sgn;
for (int i = 0; i < num.size(); i++)
if (num[i] != rhs.num[i])
return (sgn ? (num[i] < rhs.num[i]) : (num[i] > rhs.num[i]));
return false;
}
bool operator > (const BigInteger &rhs) const { return rhs < *this; }
bool operator <= (const BigInteger &rhs) const { return !(*this > rhs); }
bool operator >= (const BigInteger &rhs) const { return !(*this < rhs); }
bool operator == (const BigInteger &rhs) const { return !(*this < rhs) && !(*this > rhs); }
bool operator != (const BigInteger &rhs) const { return !(*this == rhs); }
operator bool() {
return num[0];
}
operator string() {
string ret;
if (!sgn) ret += "-";
for (int i = 0; i < num.size(); i++) {
ret += num[i] + '0';
}
return ret;
}
operator int() {
int ret = 0;
for (int i = 0; i < num.size(); i++) ret = ret * 10 + num[i];
return ret;
}
operator long long() {
long long ret = 0;
for (int i = 0; i < num.size(); i++) ret = ret * 10 + num[i];
return ret;
}
friend istream& operator >> (istream& in, BigInteger &lhs) {
string init;
in >> init;
lhs = init;
return in;
}
friend ostream& operator << (ostream& out, BigInteger lhs) {
out << (string) lhs;
return out;
}
friend BigInteger operator + (BigInteger, BigInteger);
friend BigInteger operator - (BigInteger, BigInteger);
friend BigInteger operator * (BigInteger, BigInteger);
};
BigInteger operator + (BigInteger lhs, BigInteger rhs) {
if (lhs.sgn && !rhs.sgn) {
rhs.sgn = true;
return lhs - rhs;
}
if (!lhs.sgn && rhs.sgn) {
lhs.sgn = true;
return rhs - lhs;
}
if (lhs.num.size() < rhs.num.size()) swap(lhs, rhs);
for (int i = 0; i < rhs.num.size(); i++)
lhs.num[lhs.num.size() - rhs.num.size() + i] += rhs.num[i];
for (int i = lhs.num.size() - 1; i > 0; i--) {
lhs.num[i - 1] += lhs.num[i] / 10;
lhs.num[i] %= 10;
}
if (lhs.num[0] >= 10) {
lhs.num.push_front(lhs.num[0] / 10);
lhs.num[1] %= 10;
}
return lhs;
}
BigInteger operator - (BigInteger lhs, BigInteger rhs) {
if (lhs.sgn && !rhs.sgn) {
rhs.sgn = true;
return lhs + rhs;
}
if (!lhs.sgn && rhs.sgn) return lhs + rhs;
if (!lhs.sgn && !rhs.sgn) {
lhs.sgn = true;
rhs.sgn = true;
return rhs - lhs;
}
if (lhs < rhs) return -(rhs - lhs);
for (int i = lhs.num.size() - rhs.num.size(); i < lhs.num.size(); i++)
lhs.num[i] -= rhs.num[rhs.num.size() + i - lhs.num.size()];
for (int i = lhs.num.size() - 1; i > 0; i--) {
while (lhs.num[i] < 0) {
lhs.num[i - 1]--;
lhs.num[i] += 10;
}
}
while (lhs.num.size() >= 2 && lhs.num[0] == 0) lhs.num.pop_front();
return lhs;
}
typedef BigInteger BigInt;
int main() {
BigInt a, b;
while (true) {
cin >> a >> b;
cout << a + b << " " << a - b << endl;
}
return 0;
}Ver2.0
#include <bits/stdc++.h>
using namespace std;
struct BigInteger {
private:
deque<int> num;
bool sgn;
public:
BigInteger operator = (long long init) {
num.clear();
if (init) {
if (init > 0) sgn = true;
else {
sgn = false;
init = -init;
}
while (init) {
num.push_front(init % 10);
init /= 10;
}
} else {
sgn = true;
num.push_back(0);
}
return *this;
}
BigInteger operator = (int init) { return (*this = (long long) init); }
BigInteger operator = (const char* s) {
num.clear();
assert(*s);
if (*s == '-') {
sgn = false;
assert(*(++s));
} else sgn = true;
while (*s) {
assert(isdigit(*s));
num.push_back(*(s++) - '0');
}
if (num.size() >= 2) assert(num[0]);
assert(sgn || num[0]);
return *this;
}
BigInteger() { *this = 0LL; }
BigInteger(int init) { *this = init; }
BigInteger(long long init) { *this = init; }
BigInteger(const char* s) { *this = s; }
BigInteger(string s) { *this = s.c_str(); }
BigInteger operator - () {
if (num[0] == 0) return *this;
BigInteger ret = *this;
ret.sgn = !ret.sgn;
return ret;
}
bool operator < (const BigInteger &rhs) const {
if (sgn != rhs.sgn) return !sgn;
if (num.size() < rhs.num.size()) return sgn;
if (num.size() > rhs.num.size()) return !sgn;
for (int i = 0; i < num.size(); i++)
if (num[i] != rhs.num[i])
return (sgn ? (num[i] < rhs.num[i]) : (num[i] > rhs.num[i]));
return false;
}
bool operator > (const BigInteger &rhs) const { return rhs < *this; }
bool operator <= (const BigInteger &rhs) const { return !(*this > rhs); }
bool operator >= (const BigInteger &rhs) const { return !(*this < rhs); }
bool operator == (const BigInteger &rhs) const { return !(*this < rhs) && !(*this > rhs); }
bool operator != (const BigInteger &rhs) const { return !(*this == rhs); }
operator bool() {
return num[0];
}
operator string() {
string ret;
if (!sgn) ret += "-";
for (int i = 0; i < num.size(); i++) {
ret += num[i] + '0';
}
return ret;
}
operator int() {
int ret = 0;
for (int i = 0; i < num.size(); i++) ret = ret * 10 + num[i];
return ret;
}
operator long long() {
long long ret = 0;
for (int i = 0; i < num.size(); i++) ret = ret * 10 + num[i];
return ret;
}
friend istream& operator >> (istream& in, BigInteger &a) {
string init;
in >> init;
a = init;
return in;
}
friend ostream& operator << (ostream& out, BigInteger a) {
out << (string) a;
return out;
}
friend BigInteger operator + (BigInteger, BigInteger);
friend BigInteger operator - (BigInteger, BigInteger);
};
BigInteger operator + (BigInteger a, BigInteger b) {
if (a.sgn && !b.sgn) {
b.sgn = true;
return a - b;
}
if (!a.sgn && b.sgn) {
a.sgn = true;
return b - a;
}
if (a.num.size() < b.num.size()) swap(a, b);
for (int i = 0; i < b.num.size(); i++)
a.num[a.num.size() - b.num.size() + i] += b.num[i];
for (int i = a.num.size() - 1; i > 0; i--) {
a.num[i - 1] += a.num[i] / 10;
a.num[i] %= 10;
}
if (a.num[0] >= 10) {
a.num.push_front(a.num[0] / 10);
a.num[1] %= 10;
}
return a;
}
BigInteger operator - (BigInteger a, BigInteger b) {
if (a.sgn && !b.sgn) {
b.sgn = true;
return a + b;
}
if (!a.sgn && b.sgn) return a + b;
if (!a.sgn && !b.sgn) {
a.sgn = true;
b.sgn = true;
return b - a;
}
if (a < b) return -(b - a);
for (int i = a.num.size() - b.num.size(); i < a.num.size(); i++)
a.num[i] -= b.num[b.num.size() + i - a.num.size()];
for (int i = a.num.size() - 1; i > 0; i--) {
while (a.num[i] < 0) {
a.num[i - 1]--;
a.num[i] += 10;
}
}
while (a.num.size() >= 2 && a.num[0] == 0) a.num.pop_front();
return a;
}
int main() {
// YOUR CODE HERE.
return 0;
}2022.3.17（Ver 1）
BigInteger实现第一部分，复值，构造函数，转换为string，long long，int，bool类型，实现正整数+正整数加法操作，取反操作。 有BUG及时通知本人（Qing_fy）。
#include <bits/stdc++.h>
using namespace std;
struct BigInteger {
private:
deque<int> num;
bool sgn;
public:
BigInteger operator = (long long init) {
num.clear();
if (init) {
if (init > 0) sgn = true;
else {
sgn = false;
init = -init;
}
while (init) {
num.push_front(init % 10);
init /= 10;
}
} else {
sgn = true;
num.push_back(0);
}
return *this;
}
BigInteger operator = (int init) { return (*this = (long long) init); }
BigInteger operator = (const char* s) {
num.clear();
assert(*s);
if (*s == '-') {
sgn = false;
assert(*(++s));
} else sgn = true;
while (*s) {
assert(isdigit(*s));
num.push_back(*(s++) - '0');
}
if (num.size() >= 2) assert(num[0]);
assert(sgn || num[0]);
return *this;
}
BigInteger() { *this = 0LL; }
BigInteger(int init) { *this = init; }
BigInteger(long long init) { *this = init; }
BigInteger(const char* s) { *this = s; }
BigInteger(string s) { *this = s.c_str(); }
BigInteger operator - () {
if (num[0] == 0) return *this;
BigInteger ret = *this;
ret.sgn = !ret.sgn;
return ret;
}
friend BigInteger operator + (BigInteger a, BigInteger b) {
if (a.num.size() < b.num.size()) swap(a, b);
for (int i = 0; i < b.num.size(); i++) a.num[a.num.size() - b.num.size() + i] += b.num[i];
for (int i = a.num.size() - 1; i > 0; i--) {
a.num[i - 1] += a.num[i] / 10;
a.num[i] %= 10;
}
if (a.num[0] >= 10) {
a.num.push_front(a.num[0] / 10);
a.num[1] %= 10;
}
return a;
}
operator bool() {
return num[0];
}
operator string() {
string ret;
if (!sgn) ret += "-";
for (int i = 0; i < num.size(); i++) {
ret += num[i] + '0';
}
return ret;
}
operator long long() {
long long ret = 0;
for (int i = 0; i < num.size(); i++) ret = ret * 10 + num[i];
return ret;
}
friend istream& operator >> (istream& in, BigInteger &a) {
string init;
in >> init;
a = init;
return in;
}
friend ostream& operator << (ostream& out, BigInteger a) {
out << (string) a;
return out;
}
};
int main() {
// YOUR CODE HERE.
return 0;
}