Длинная арифметика
Перейти к навигации
Перейти к поиску
Хранение, ввод и вывод
class BigInteger {
static const int BASE = 1e9;
static const int BASE_LEN = 9;
static const int MAX_SIZE = 1e4;
int d[MAX_SIZE];
int size;
public:
BigInteger(long long val = 0) {
for (int i = 0; i < MAX_SIZE; i++)
d[i] = 0;
size = 0;
if (val == 0)
d[size++] = 0;
while (val > 0) {
d[size++] = val % BASE;
val /= BASE;
}
}
BigInteger(char val[]) {
for (int i = 0; i < MAX_SIZE; i++)
d[i] = 0;
size = 0;
for (int i = strlen(val) - 1; i >= 0; i -= BASE_LEN) {
int digit = 0;
for (int j = max(0, i - BASE_LEN + 1); j <= i; j++)
digit = digit * 10 + val[j] - '0';
d[size++] = digit;
}
}
void print() const {
static char spec[] = "%00d";
spec[2] = BASE_LEN + '0';
printf("%d", d[size - 1]);
for (int i = size - 2; i >= 0; i--)
printf(spec, d[i]);
}
};
Сравнение
int cmp(const BigInteger &that) const {
if (size != that.size)
return size < that.size ? -1 : 1;
for (int i = size - 1; i >= 0; i--) {
if (d[i] != that.d[i])
return d[i] < that.d[i] ? -1 : 1;
}
return 0;
}
bool operator < (const BigInteger &that) const {
return cmp(that) < 0;
}
bool operator == (const BigInteger &that) const {
return cmp(that) == 0;
}
Сложение
BigInteger operator + (const BigInteger &that) const {
BigInteger res;
int carry = 0;
for (int i = 0; i < max(size, that.size) || carry != 0; i++) {
long long x = 0LL + d[i] + that.d[i] + carry;
res.d[i] = x % BASE;
carry = x / BASE;
}
res.size = max(size, that.size) + 1;
while (res.size > 1 && res.d[res.size - 1] == 0)
res.size--;
return res;
}
Вычитание
Предполагается, что уменьшаемое больше вычитаемого.
BigInteger operator - (const BigInteger &that) const {
BigInteger res;
int carry = 0;
for (int i = 0; i < size || carry != 0; i++) {
long long x = 0LL + d[i] - that.d[i] + carry;
res.d[i] = (x + BASE) % BASE;
carry = x < 0 ? -1 : 0;
}
res.size = size;
while (res.size > 1 && res.d[res.size - 1] == 0)
res.size--;
return res;
}
Умножение
BigInteger operator * (const BigInteger &that) const {
BigInteger res;
for (int i = 0; i < size; i++) {
int carry = 0;
for (int j = 0; j < that.size || carry != 0; j++) {
long long x = res.d[i + j] + 1LL * d[i] * that.d[j] + carry;
res.d[i + j] = x % BASE;
carry = x / BASE;
}
}
res.size = size + that.size;
while (res.size > 1 && res.d[res.size - 1] == 0)
res.size--;
return res;
}
|
BigInteger operator * (int that) const {
BigInteger res;
int carry = 0;
for (int i = 0; i < size || carry != 0; i++) {
long long x = 1LL * d[i] * that + carry;
res.d[i] = x % BASE;
carry = x / BASE;
}
res.size = size + 1;
while (res.size > 1 && res.d[res.size - 1] == 0)
res.size--;
return res;
}
|
Деление и взятие остатка
BigInteger operator / (const BigInteger &that) const {
BigInteger res, carry;
for (int i = size - 1; i >= 0; i--) {
carry = carry * BASE;
carry.d[0] = d[i];
int l = 0, r = BASE - 1, m;
while (l + 1 < r) {
m = l + (r - l) / 2;
if ((that * m).cmp(carry) <= 0)
l = m;
else
r = m;
}
res.d[i] = (that * r).cmp(carry) <= 0 ? r : l;
carry = carry - that * res.d[i];
}
res.size = size;
while (res.size > 1 && res.d[res.size - 1] == 0)
res.size--;
return res;
}
|
BigInteger operator / (int that) const {
BigInteger res;
int carry = 0;
for (int i = size - 1; i >= 0; i--) {
long long x = 1LL * carry * BASE + d[i];
res.d[i] = x / that;
carry = x % that;
}
res.size = size;
while (res.size > 1 && res.d[res.size - 1] == 0)
res.size--;
return res;
}
|
BigInteger operator % (const BigInteger &that) const {
BigInteger carry;
for (int i = size - 1; i >= 0; i--) {
carry = carry * BASE;
carry.d[0] = d[i];
int l = 0, r = BASE - 1, m;
while (l + 1 < r) {
m = l + (r - l) / 2;
if ((that * m).cmp(carry) <= 0)
l = m;
else
r = m;
}
int digit = (that * r).cmp(carry) <= 0 ? r : l;
carry = carry - that * digit;
}
return carry;
}
|
int operator % (int that) const {
int carry = 0;
for (int i = size - 1; i >= 0; i--)
carry = (1LL * carry * BASE + d[i]) % that;
return carry;
}
|
Длинная арифметика на vector
struct BigInteger {
vector<int> digits;
inline static const int BASE = 1e9;
inline static const int DIGIT_WIDTH = 9;
inline int digit(int index) const {
return index < digits.size() ? digits[index] : 0;
}
inline int &digit(int index) {
if (digits.size() <= index)
digits.resize(index + 1);
return digits[index];
}
inline void removeZeros() {
while (!digits.empty() && !digits.back())
digits.pop_back();
}
BigInteger(long long value = 0) {
for (; value; value /= BASE)
digits.push_back(value % BASE);
}
BigInteger(const string &s) {
for (int r = s.size() - 1; r >= 0; r -= DIGIT_WIDTH) {
int l = max(r - DIGIT_WIDTH + 1, 0);
digits.push_back(stoi(s.substr(l, r - l + 1)));
}
removeZeros();
}
BigInteger operator + (const BigInteger &that) const {
BigInteger res;
for (int i = 0, carry = 0; i < digits.size() || i < that.digits.size() || carry; i++) {
int cur = digit(i) + that.digit(i) + carry;
res.digits.push_back(cur % BASE);
carry = cur / BASE;
}
return res;
}
BigInteger operator * (const BigInteger &that) const {
BigInteger res;
for (int i = 0, carry = 0; i < digits.size(); i++) {
for (int j = 0; j < that.digits.size() || carry; j++) {
long long cur = res.digit(i + j) + 1LL * digit(i) * that.digit(j) + carry;
res.digit(i + j) = cur % BASE;
carry = cur / BASE;
}
}
res.removeZeros();
return res;
}
BigInteger operator / (int that) const {
BigInteger res;
for (int i = digits.size() - 1, carry = 0; i >= 0; i--) {
long long cur = 1LL * carry * BASE + digit(i);
res.digit(i) = cur / that;
carry = cur % that;
}
res.removeZeros();
return res;
}
friend istream &operator >> (istream &in, BigInteger &value) {
string s;
in >> s;
value = BigInteger(s);
return in;
}
friend ostream &operator << (ostream &out, const BigInteger &value) {
if (value.digits.empty()) {
out << 0;
} else {
out << value.digits.back();
for (int i = (int)value.digits.size() - 2; i >= 0; i--) {
out.width(DIGIT_WIDTH);
out.fill('0');
out << value.digits[i];
}
}
return out;
}
};