Длинная арифметика: различия между версиями
Перейти к навигации
Перейти к поиску
Ctrlalt (обсуждение | вклад) Нет описания правки |
Ctrlalt (обсуждение | вклад) Нет описания правки |
||
(не показано 7 промежуточных версий этого же участника) | |||
Строка 1: | Строка 1: | ||
== Хранение, ввод и вывод == | |||
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; | |||
} | |||
== Умножение == | |||
{| | |||
| width="50%" | | |||
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; | |||
} | |||
| width="10px" | | |||
| width="50%" | | |||
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; | |||
} | |||
|} | |||
== Деление и взятие остатка == | |||
{| | |||
| width="50%" | | |||
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; | |||
} | |||
| width="10px" | | |||
| width="50%" | | |||
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; | |||
} | |||
|} | |||
{| | |||
| width="50%" | | |||
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; | |||
} | |||
| width="10px" | | |||
| width="50%" | | |||
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; | |||
} | |||
|} | |||
== Ссылки на задачи == | == Ссылки на задачи == | ||
* [http://acmp.ru/?main=task&id_task=103 ACMP #103 — Снова A + B] | * [http://acmp.ru/?main=task&id_task=103 ACMP #103 — Снова A + B] | ||
Строка 6: | Строка 227: | ||
== Ссылки == | == Ссылки == | ||
* [[Сложная длинная арифметика]] | |||
* [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 — Длинная арифметика] | ||
* [http://brestprog.neocities.org/lections/longarithmetics.html brestprog.neocities.org — Длинная арифметика] | |||
* [http://informatics.mccme.ru/course/view.php?id=17 informatics.mccme.ru — Курс «Арифметика и числовые алгоритмы» — часть 5] | * [http://informatics.mccme.ru/course/view.php?id=17 informatics.mccme.ru — Курс «Арифметика и числовые алгоритмы» — часть 5] | ||
* [http://github.com/ADJA/algos/blob/master/NumberTheory/BigInt.cpp Algos — Structure implementing long arithmetic in C++] | |||
[[Category:Арифметические алгоритмы]] | [[Category:Арифметические алгоритмы]] |
Текущая версия от 17:41, 26 июля 2018
Хранение, ввод и вывод
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; } |