Длинная арифметика: различия между версиями
Перейти к навигации
Перейти к поиску
Ctrlalt (обсуждение | вклад) (→Ссылки) |
Ctrlalt (обсуждение | вклад) Нет описания правки |
||
(не показаны 2 промежуточные версии этого же участника) | |||
Строка 2: | Строка 2: | ||
class BigInteger { | class BigInteger { | ||
static const int BASE = 1e9; | static const int BASE = 1e9; | ||
static const int BASE_LEN = 9; | static const int BASE_LEN = 9; | ||
Строка 8: | Строка 7: | ||
int d[MAX_SIZE]; | int d[MAX_SIZE]; | ||
int size; | int size; | ||
public: | public: | ||
BigInteger(long long val = 0) { | |||
BigInteger(long long val) { | |||
for (int i = 0; i < MAX_SIZE; i++) | for (int i = 0; i < MAX_SIZE; i++) | ||
d[i] = 0; | d[i] = 0; | ||
Строка 22: | Строка 19: | ||
} | } | ||
} | } | ||
BigInteger(char val[]) { | BigInteger(char val[]) { | ||
for (int i = 0; i < MAX_SIZE; i++) | for (int i = 0; i < MAX_SIZE; i++) | ||
Строка 34: | Строка 30: | ||
} | } | ||
} | } | ||
void print() const { | void print() const { | ||
static char spec[] = "%00d"; | static char spec[] = "%00d"; | ||
Строка 42: | Строка 37: | ||
printf(spec, d[i]); | printf(spec, d[i]); | ||
} | } | ||
}; | }; | ||
Строка 55: | Строка 49: | ||
} | } | ||
return 0; | return 0; | ||
} | |||
bool operator < (const BigInteger &that) const { | |||
return cmp(that) < 0; | |||
} | |||
bool operator == (const BigInteger &that) const { | |||
return cmp(that) == 0; | |||
} | } | ||
== Сложение == | == Сложение == | ||
BigInteger | BigInteger operator + (const BigInteger &that) const { | ||
BigInteger res | BigInteger res; | ||
int carry = 0; | int carry = 0; | ||
for (int i = 0; i < max(size, that.size) || carry != 0; i++) { | for (int i = 0; i < max(size, that.size) || carry != 0; i++) { | ||
Строка 77: | Строка 77: | ||
Предполагается, что уменьшаемое больше вычитаемого. | Предполагается, что уменьшаемое больше вычитаемого. | ||
BigInteger | BigInteger operator - (const BigInteger &that) const { | ||
BigInteger res | BigInteger res; | ||
int carry = 0; | int carry = 0; | ||
for (int i = 0; i < size || carry != 0; i++) { | for (int i = 0; i < size || carry != 0; i++) { | ||
Строка 95: | Строка 95: | ||
{| | {| | ||
| width="50%" | | | width="50%" | | ||
BigInteger | BigInteger operator * (const BigInteger &that) const { | ||
BigInteger res | BigInteger res; | ||
for (int i = 0; i < size; i++) { | for (int i = 0; i < size; i++) { | ||
int carry = 0; | int carry = 0; | ||
Строка 112: | Строка 112: | ||
| width="10px" | | | width="10px" | | ||
| width="50%" | | | width="50%" | | ||
BigInteger | BigInteger operator * (int that) const { | ||
BigInteger res | BigInteger res; | ||
int carry = 0; | int carry = 0; | ||
for (int i = 0; i < size || carry != 0; i++) { | for (int i = 0; i < size || carry != 0; i++) { | ||
Строка 133: | Строка 133: | ||
{| | {| | ||
| width="50%" | | | width="50%" | | ||
BigInteger | BigInteger operator / (const BigInteger &that) const { | ||
BigInteger res | BigInteger res, carry; | ||
for (int i = size - 1; i >= 0; i--) { | for (int i = size - 1; i >= 0; i--) { | ||
carry = carry | carry = carry * BASE; | ||
carry.d[0] = d[i]; | carry.d[0] = d[i]; | ||
int l = 0, r = BASE - 1, m; | int l = 0, r = BASE - 1, m; | ||
while (l + 1 < r) { | while (l + 1 < r) { | ||
m = l + (r - l) / 2; | m = l + (r - l) / 2; | ||
if (that | if ((that * m).cmp(carry) <= 0) | ||
l = m; | l = m; | ||
else | else | ||
r = m; | r = m; | ||
} | } | ||
res.d[i] = that | res.d[i] = (that * r).cmp(carry) <= 0 ? r : l; | ||
carry = carry | carry = carry - that * res.d[i]; | ||
} | } | ||
res.size = size; | res.size = size; | ||
Строка 156: | Строка 156: | ||
| width="10px" | | | width="10px" | | ||
| width="50%" | | | width="50%" | | ||
BigInteger | BigInteger operator / (int that) const { | ||
BigInteger res | BigInteger res; | ||
int carry = 0; | int carry = 0; | ||
for (int i = size - 1; i >= 0; i--) { | for (int i = size - 1; i >= 0; i--) { | ||
Строка 180: | Строка 180: | ||
{| | {| | ||
| width="50%" | | | width="50%" | | ||
BigInteger | BigInteger operator % (const BigInteger &that) const { | ||
BigInteger carry | BigInteger carry; | ||
for (int i = size - 1; i >= 0; i--) { | for (int i = size - 1; i >= 0; i--) { | ||
carry = carry | carry = carry * BASE; | ||
carry.d[0] = d[i]; | carry.d[0] = d[i]; | ||
int l = 0, r = BASE - 1, m; | int l = 0, r = BASE - 1, m; | ||
while (l + 1 < r) { | while (l + 1 < r) { | ||
m = l + (r - l) / 2; | m = l + (r - l) / 2; | ||
if (that | if ((that * m).cmp(carry) <= 0) | ||
l = m; | l = m; | ||
else | else | ||
r = m; | r = m; | ||
} | } | ||
int digit = that | int digit = (that * r).cmp(carry) <= 0 ? r : l; | ||
carry = carry | carry = carry - that * digit; | ||
} | } | ||
return carry; | return carry; | ||
Строка 200: | Строка 200: | ||
| width="10px" | | | width="10px" | | ||
| width="50%" | | | width="50%" | | ||
int | int operator % (int that) const { | ||
int carry = 0; | int carry = 0; | ||
for (int i = size - 1; i >= 0; i--) | for (int i = size - 1; i >= 0; i--) | ||
Строка 219: | Строка 219: | ||
|} | |} | ||
== Длинная арифметика на vector == | |||
struct BigInteger { | |||
vector<int> digits; | |||
BigInteger(long long value = 0) { | |||
for ( ; value; value /= 10) | |||
digits.push_back(value % 10); | |||
} | |||
BigInteger operator + (const BigInteger &that) const { | |||
BigInteger res; | |||
for (int i = 0, carry = 0; i < digits.size() || i < that.digits.size() || carry; i++) { | |||
int digit = i < digits.size() ? digits[i] : 0; | |||
int thatDigit = i < that.digits.size() ? that.digits[i] : 0; | |||
int sum = digit + thatDigit + carry; | |||
res.digits.push_back(sum % 10); | |||
carry = sum / 10; | |||
} | |||
return res; | |||
} | |||
friend ostream &operator << (ostream &out, const BigInteger &value) { | |||
if (value.digits.empty()) { | |||
out << 0; | |||
} else { | |||
for (int i = value.digits.size() - 1; i >= 0; i--) | |||
out << value.digits[i]; | |||
} | |||
return out; | |||
} | |||
}; | |||
== Ссылки на задачи == | == Ссылки на задачи == | ||
Строка 227: | Строка 260: | ||
== Ссылки == | == Ссылки == | ||
* [[Сложная длинная арифметика]] | |||
* [http://e-maxx.ru/algo/big_integer e-maxx.ru — Длинная арифметика] | * [http://e-maxx.ru/algo/big_integer e-maxx.ru — Длинная арифметика] | ||
* [http://cppalgo.blogspot.ru/2010/05/blog-post.html cppalgo.blogspot.ru — Длинная арифметика] | * [http://cppalgo.blogspot.ru/2010/05/blog-post.html cppalgo.blogspot.ru — Длинная арифметика] |
Версия от 14:16, 21 июля 2024
Хранение, ввод и вывод
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; BigInteger(long long value = 0) { for ( ; value; value /= 10) digits.push_back(value % 10); } BigInteger operator + (const BigInteger &that) const { BigInteger res; for (int i = 0, carry = 0; i < digits.size() || i < that.digits.size() || carry; i++) { int digit = i < digits.size() ? digits[i] : 0; int thatDigit = i < that.digits.size() ? that.digits[i] : 0; int sum = digit + thatDigit + carry; res.digits.push_back(sum % 10); carry = sum / 10; } return res; } friend ostream &operator << (ostream &out, const BigInteger &value) { if (value.digits.empty()) { out << 0; } else { for (int i = value.digits.size() - 1; i >= 0; i--) out << value.digits[i]; } return out; } };