Длинная арифметика - История изменений

Ctrlalt: /* Длинная арифметика на vector */

2025-10-04T14:22:52Z

Длинная арифметика на vector

@@ Строка 271: / Строка 271: @@
               carry = cur / BASE;
+          }
           return res;
+      }

2025-04-13T19:01:11Z

Длинная арифметика на vector

← Предыдущая версия		Версия от 19:01, 13 апреля 2025
Строка 254:		Строка 254:
	removeZeros();		removeZeros();
	}		}

	bool operator < (const BigInteger &that) const {		bool operator < (const BigInteger &that) const {
	if (digits.size() != that.digits.size())		if (digits.size() != that.digits.size())
Строка 297:		Строка 297:
	return res;		return res;
	}		}

	int operator % (int that) const {		int operator % (int that) const {
	long long res = 0;		long long res = 0;

2025-04-13T19:00:53Z

Длинная арифметика на vector

@@ Строка 253: / Строка 253: @@
+          }
           removeZeros();
+      }
@@ Строка 286: / Строка 295: @@
+          }
           res.removeZeros();
           return res;
+      }

2024-08-13T23:40:05Z

Длинная арифметика на vector

@@ Строка 224: / Строка 224: @@
   struct BigInteger {
       vector<int> digits;
       BigInteger(long long value = 0) {
-          for ( ; value; value /= 10)
+          for (; value; value /= BASE)
-              digits.push_back(value % 10);
+              digits.push_back(value % BASE);
+      }
@@ Строка 233: / Строка 258: @@
           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 cur = digit(i) + that.digit(i) + carry;
-             int thatDigit = i < that.digits.size() ? that.digits[i] : 0;
+              res.digits.push_back(cur % BASE);
-             int sum = digit + thatDigit + carry;
+              carry = cur / BASE;
+          }
           return res;
+      }
@@ Строка 246: / Строка 300: @@
               out << 0;
           } else {
-              for (int i = value.digits.size() - 1; i >= 0; i--)
+             out << value.digits.back();
                   out << value.digits[i];
+          }
           return out;

2024-07-21T14:16:00Z

← Предыдущая версия		Версия от 14:16, 21 июля 2024
Строка 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;
			}
			};

	== Ссылки на задачи ==		== Ссылки на задачи ==

2018-07-26T17:41:04Z

← Предыдущая версия		Версия от 17:41, 26 июля 2018
Строка 227:		Строка 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 — Длинная арифметика]

2018-07-25T20:29:04Z

2016-01-27T20:07:50Z

Ссылки

← Предыдущая версия		Версия от 20:07, 27 января 2016
Строка 229:		Строка 229:
	* [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++]		* [http://github.com/ADJA/algos/blob/master/NumberTheory/BigInt.cpp Algos — Structure implementing long arithmetic in C++]

	[[Category:Арифметические алгоритмы]]		[[Category:Арифметические алгоритмы]]

2014-08-19T04:30:05Z

Ссылки

← Предыдущая версия		Версия от 04:30, 19 августа 2014
Строка 230:		Строка 230:
	* [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://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:Арифметические алгоритмы]]

2014-08-16T23:05:38Z

Умножение

← Предыдущая версия		Версия от 23:05, 16 августа 2014
Строка 97:		Строка 97:
	BigInteger mul(const BigInteger &that) const {		BigInteger mul(const BigInteger &that) const {
	BigInteger res(0LL);		BigInteger res(0LL);
	for (int i = 0; i < size; i++) ~~const~~ {		for (int i = 0; i < size; i++) {
	int carry = 0;		int carry = 0;
	for (int j = 0; j < that.size \|\| carry != 0; j++) {		for (int j = 0; j < that.size \|\| carry != 0; j++) {