commit 5bb42f4e2755debb7434d1b90db3d53169ce5df8
parent 6403a87d3789e14d58a7e9aeffbaadd6bd58f810
Author: Antoine Amarilli <a3nm@a3nm.net>
Date: Sun, 12 Mar 2017 11:00:38 +0100
bigint
Diffstat:
| InfInt.h | | | 1370 | +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ |
| calc.cpp | | | 40 | ++++++++++++++++++++++++---------------- |
2 files changed, 1394 insertions(+), 16 deletions(-)
diff --git a/InfInt.h b/InfInt.h
@@ -0,0 +1,1370 @@
+// http://stackoverflow.com/a/6321977/414272
+#ifdef __GNUC__
+// Avoid tons of warnings with root code
+#pragma GCC system_header
+#endif
+/*
+ * InfInt - Arbitrary-Precision Integer Arithmetic Library
+ * Copyright (C) 2013 Sercan Tutar
+ *
+ * This Source Code Form is subject to the terms of the Mozilla Public
+ * License, v. 2.0. If a copy of the MPL was not distributed with this
+ * file, You can obtain one at http://mozilla.org/MPL/2.0/.
+ *
+ *
+ * USAGE:
+ * It is pretty straight forward to use the library. Just create an instance of
+ * InfInt class and start using it.
+ *
+ * Useful methods:
+ * intSqrt: integer square root operation
+ * digitAt: returns digit at index
+ * numberOfDigits: returns number of digits
+ * size: returns size in bytes
+ * toString: converts it to a string
+ *
+ * There are also conversion methods which allow conversion to primitive types:
+ * toInt, toLong, toLongLong, toUnsignedInt, toUnsignedLong, toUnsignedLongLong.
+ *
+ * You may define INFINT_USE_EXCEPTIONS and library methods will start raising
+ * InfIntException in case of error instead of writing error messages using
+ * std::cerr.
+ *
+ * See ReadMe.txt for more info.
+ *
+ *
+ * No overflows, happy programmers!
+ *
+ */
+
+#ifndef INFINT_H_
+#define INFINT_H_
+
+#include <iostream>
+#include <vector>
+#include <sstream>
+#include <iomanip>
+
+//#include <limits.h>
+//#include <stdlib.h>
+
+#ifdef _WIN32
+#define LONG_LONG_MIN LLONG_MIN
+#define LONG_LONG_MAX LLONG_MAX
+#define ULONG_LONG_MAX ULLONG_MAX
+#endif
+
+#ifdef INFINT_USE_EXCEPTIONS
+#include <exception>
+#endif
+
+typedef int ELEM_TYPE;
+typedef long long PRODUCT_TYPE;
+static const ELEM_TYPE BASE = 1000000000;
+static const ELEM_TYPE UPPER_BOUND = 999999999;
+static const ELEM_TYPE DIGIT_COUNT = 9;
+static const int powersOfTen[] = { 1, 10, 100, 1000, 10000, 100000, 1000000, 10000000, 100000000 };
+
+#ifdef INFINT_USE_EXCEPTIONS
+class InfIntException: public std::exception
+{
+public:
+ InfIntException(const std::string& txt) throw ();
+ ~InfIntException() throw ();
+ const char* what() const throw ();
+private:
+ std::string txt;
+};
+
+InfIntException::InfIntException(const std::string& txt) throw () :
+std::exception(), txt(txt)
+{
+}
+
+InfIntException::~InfIntException() throw ()
+{
+}
+
+const char* InfIntException::what() const throw ()
+{
+ return txt.c_str();
+}
+#endif
+
+inline static div_t my_div(int num, int denom)
+{
+ div_t result;
+ result.quot = num / denom;
+ result.rem = num - denom * result.quot;
+ return result;
+}
+
+inline static ldiv_t my_ldiv(long num, long denom)
+{
+ ldiv_t result;
+ result.quot = num / denom;
+ result.rem = num - denom * result.quot;
+ return result;
+}
+
+inline static lldiv_t my_lldiv(long long num, long long denom)
+{
+ lldiv_t result;
+ result.quot = num / denom;
+ result.rem = num - denom * result.quot;
+ return result;
+}
+
+class InfInt
+{
+ friend std::ostream& operator<<(std::ostream &s, const InfInt &n);
+ friend std::istream& operator>>(std::istream &s, InfInt &val);
+
+public:
+ /* constructors */
+ InfInt();
+ InfInt(const char* c);
+ InfInt(const std::string& s);
+ InfInt(int l);
+ InfInt(long l);
+ InfInt(long long l);
+ InfInt(unsigned int l);
+ InfInt(unsigned long l);
+ InfInt(unsigned long long l);
+ InfInt(const InfInt& l);
+
+ /* assignment operators */
+ const InfInt& operator=(const char* c);
+ const InfInt& operator=(const std::string& s);
+ const InfInt& operator=(int l);
+ const InfInt& operator=(long l);
+ const InfInt& operator=(long long l);
+ const InfInt& operator=(unsigned int l);
+ const InfInt& operator=(unsigned long l);
+ const InfInt& operator=(unsigned long long l);
+ const InfInt& operator=(const InfInt& l);
+
+ /* unary increment/decrement operators */
+ const InfInt& operator++();
+ const InfInt& operator--();
+ InfInt operator++(int);
+ InfInt operator--(int);
+
+ /* operational assignments */
+ const InfInt& operator+=(const InfInt& rhs);
+ const InfInt& operator-=(const InfInt& rhs);
+ const InfInt& operator*=(const InfInt& rhs);
+ const InfInt& operator/=(const InfInt& rhs); // throw
+ const InfInt& operator%=(const InfInt& rhs); // throw
+ const InfInt& operator*=(ELEM_TYPE rhs);
+
+ /* operations */
+ InfInt operator-() const;
+ InfInt operator+(const InfInt& rhs) const;
+ InfInt operator-(const InfInt& rhs) const;
+ InfInt operator*(const InfInt& rhs) const;
+ InfInt operator/(const InfInt& rhs) const; // throw
+ InfInt operator%(const InfInt& rhs) const; // throw
+ InfInt operator*(ELEM_TYPE rhs) const;
+
+ /* relational operations */
+ bool operator==(const InfInt& rhs) const;
+ bool operator!=(const InfInt& rhs) const;
+ bool operator<(const InfInt& rhs) const;
+ bool operator<=(const InfInt& rhs) const;
+ bool operator>(const InfInt& rhs) const;
+ bool operator>=(const InfInt& rhs) const;
+
+ /* integer square root */
+ InfInt intSqrt() const; // throw
+
+ /* digit operations */
+ char digitAt(size_t i) const; // throw
+ size_t numberOfDigits() const;
+
+ /* size in bytes */
+ size_t size() const;
+
+ /* string conversion */
+ std::string toString() const;
+
+ /* conversion to primitive types */
+ int toInt() const; // throw
+ long toLong() const; // throw
+ long long toLongLong() const; // throw
+ unsigned int toUnsignedInt() const; // throw
+ unsigned long toUnsignedLong() const; // throw
+ unsigned long long toUnsignedLongLong() const; // throw
+
+private:
+ static ELEM_TYPE dInR(const InfInt& R, const InfInt& D);
+ static void multiplyByDigit(ELEM_TYPE factor, std::vector<ELEM_TYPE>& val);
+
+ void correct(bool justCheckLeadingZeros = false, bool hasValidSign = false);
+ void fromString(const std::string& s);
+ void optimizeSqrtSearchBounds(InfInt& lo, InfInt& hi) const;
+ void truncateToBase();
+ bool equalizeSigns();
+ void removeLeadingZeros();
+
+ std::vector<ELEM_TYPE> val; // number with base FACTOR
+ bool pos; // true if number is positive
+};
+
+inline InfInt::InfInt() : pos(true)
+{
+ //PROFINY_SCOPE
+ val.push_back((ELEM_TYPE) 0);
+}
+
+inline InfInt::InfInt(const char* c)
+{
+ //PROFINY_SCOPE
+ fromString(c);
+}
+
+inline InfInt::InfInt(const std::string& s)
+{
+ //PROFINY_SCOPE
+ fromString(s);
+}
+
+inline InfInt::InfInt(int l) : pos(l >= 0)
+{
+ //PROFINY_SCOPE
+ bool subtractOne = false;
+ if (l == INT_MIN)
+ {
+ subtractOne = true;
+ ++l;
+ }
+
+ if (!pos)
+ {
+ l = -l;
+ }
+ do
+ {
+ div_t dt = my_div(l, BASE);
+ val.push_back((ELEM_TYPE) dt.rem);
+ l = dt.quot;
+ } while (l > 0);
+
+ if (subtractOne)
+ {
+ --*this;
+ }
+}
+
+inline InfInt::InfInt(long l) : pos(l >= 0)
+{
+ //PROFINY_SCOPE
+ bool subtractOne = false;
+ if (l == LONG_MIN)
+ {
+ subtractOne = true;
+ ++l;
+ }
+
+ if (!pos)
+ {
+ l = -l;
+ }
+ do
+ {
+ ldiv_t dt = my_ldiv(l, BASE);
+ val.push_back((ELEM_TYPE) dt.rem);
+ l = dt.quot;
+ } while (l > 0);
+
+ if (subtractOne)
+ {
+ --*this;
+ }
+}
+
+inline InfInt::InfInt(long long l) : pos(l >= 0)
+{
+ //PROFINY_SCOPE
+ bool subtractOne = false;
+ if (l == LONG_LONG_MIN)
+ {
+ subtractOne = true;
+ ++l;
+ }
+
+ if (!pos)
+ {
+ l = -l;
+ }
+ do
+ {
+ lldiv_t dt = my_lldiv(l, BASE);
+ val.push_back((ELEM_TYPE) dt.rem);
+ l = dt.quot;
+ } while (l > 0);
+
+ if (subtractOne)
+ {
+ --*this;
+ }
+}
+
+inline InfInt::InfInt(unsigned int l) : pos(true)
+{
+ //PROFINY_SCOPE
+ do
+ {
+ val.push_back((ELEM_TYPE) (l % BASE));
+ l = l / BASE;
+ } while (l > 0);
+}
+
+inline InfInt::InfInt(unsigned long l) : pos(true)
+{
+ //PROFINY_SCOPE
+ do
+ {
+ val.push_back((ELEM_TYPE) (l % BASE));
+ l = l / BASE;
+ } while (l > 0);
+}
+
+inline InfInt::InfInt(unsigned long long l) : pos(true)
+{
+ //PROFINY_SCOPE
+ do
+ {
+ val.push_back((ELEM_TYPE) (l % BASE));
+ l = l / BASE;
+ } while (l > 0);
+}
+
+inline InfInt::InfInt(const InfInt& l) : pos(l.pos), val(l.val)
+{
+ //PROFINY_SCOPE
+}
+
+inline const InfInt& InfInt::operator=(const char* c)
+{
+ //PROFINY_SCOPE
+ fromString(c);
+ return *this;
+}
+
+inline const InfInt& InfInt::operator=(const std::string& s)
+{
+ //PROFINY_SCOPE
+ fromString(s);
+ return *this;
+}
+
+inline const InfInt& InfInt::operator=(int l)
+{
+ //PROFINY_SCOPE
+ bool subtractOne = false;
+ if (l == INT_MIN)
+ {
+ subtractOne = true;
+ ++l;
+ }
+
+ pos = l >= 0;
+ val.clear();
+ if (!pos)
+ {
+ l = -l;
+ }
+ do
+ {
+ div_t dt = my_div(l, BASE);
+ val.push_back((ELEM_TYPE) dt.rem);
+ l = dt.quot;
+ } while (l > 0);
+
+ return subtractOne ? --*this : *this;
+}
+
+inline const InfInt& InfInt::operator=(long l)
+{
+ //PROFINY_SCOPE
+ bool subtractOne = false;
+ if (l == LONG_MIN)
+ {
+ subtractOne = true;
+ ++l;
+ }
+
+ pos = l >= 0;
+ val.clear();
+ if (!pos)
+ {
+ l = -l;
+ }
+ do
+ {
+ ldiv_t dt = my_ldiv(l, BASE);
+ val.push_back((ELEM_TYPE) dt.rem);
+ l = dt.quot;
+ } while (l > 0);
+
+ return subtractOne ? --*this : *this;
+}
+
+inline const InfInt& InfInt::operator=(long long l)
+{
+ //PROFINY_SCOPE
+ bool subtractOne = false;
+ if (l == LONG_LONG_MIN)
+ {
+ subtractOne = true;
+ ++l;
+ }
+
+ pos = l >= 0;
+ val.clear();
+ if (!pos)
+ {
+ l = -l;
+ }
+ do
+ {
+ lldiv_t dt = my_lldiv(l, BASE);
+ val.push_back((ELEM_TYPE) dt.rem);
+ l = dt.quot;
+ } while (l > 0);
+
+ return subtractOne ? --*this : *this;
+}
+
+inline const InfInt& InfInt::operator=(unsigned int l)
+{
+ //PROFINY_SCOPE
+ pos = true;
+ val.clear();
+ do
+ {
+ val.push_back((ELEM_TYPE) (l % BASE));
+ l = l / BASE;
+ } while (l > 0);
+ return *this;
+}
+
+inline const InfInt& InfInt::operator=(unsigned long l)
+{
+ //PROFINY_SCOPE
+ pos = true;
+ val.clear();
+ do
+ {
+ val.push_back((ELEM_TYPE) (l % BASE));
+ l = l / BASE;
+ } while (l > 0);
+ return *this;
+}
+
+inline const InfInt& InfInt::operator=(unsigned long long l)
+{
+ //PROFINY_SCOPE
+ pos = true;
+ val.clear();
+ do
+ {
+ val.push_back((ELEM_TYPE) (l % BASE));
+ l = l / BASE;
+ } while (l > 0);
+ return *this;
+}
+
+const InfInt& InfInt::operator=(const InfInt& l)
+{
+ //PROFINY_SCOPE
+ pos = l.pos;
+ val = l.val;
+ return *this;
+}
+
+inline const InfInt& InfInt::operator++()
+{
+ //PROFINY_SCOPE
+ val[0] += (pos ? 1 : -1);
+ this->correct(false, true);
+ return *this;
+}
+
+inline const InfInt& InfInt::operator--()
+{
+ //PROFINY_SCOPE
+ val[0] -= (pos ? 1 : -1);
+ this->correct(false, true);
+ return *this;
+}
+
+inline InfInt InfInt::operator++(int)
+{
+ //PROFINY_SCOPE
+ InfInt result = *this;
+ val[0] += (pos ? 1 : -1);
+ this->correct(false, true);
+ return result;
+}
+
+inline InfInt InfInt::operator--(int)
+{
+ //PROFINY_SCOPE
+ InfInt result = *this;
+ val[0] -= (pos ? 1 : -1);
+ this->correct(false, true);
+ return result;
+}
+
+inline const InfInt& InfInt::operator+=(const InfInt& rhs)
+{
+ //PROFINY_SCOPE
+ if (rhs.val.size() > val.size())
+ {
+ val.resize(rhs.val.size(), 0);
+ }
+ for (size_t i = 0; i < val.size(); ++i)
+ {
+ val[i] = (pos ? val[i] : -val[i]) + (i < rhs.val.size() ? (rhs.pos ? rhs.val[i] : -rhs.val[i]) : 0);
+ }
+ correct();
+ return *this;
+}
+
+inline const InfInt& InfInt::operator-=(const InfInt& rhs)
+{
+ //PROFINY_SCOPE
+ if (rhs.val.size() > val.size())
+ {
+ val.resize(rhs.val.size(), 0);
+ }
+ for (size_t i = 0; i < val.size(); ++i)
+ {
+ val[i] = (pos ? val[i] : -val[i]) - (i < rhs.val.size() ? (rhs.pos ? rhs.val[i] : -rhs.val[i]) : 0);
+ }
+ correct();
+ return *this;
+}
+
+inline const InfInt& InfInt::operator*=(const InfInt& rhs)
+{
+ //PROFINY_SCOPE
+ // TODO: optimize (do not use operator*)
+ *this = *this * rhs;
+ return *this;
+}
+
+inline const InfInt& InfInt::operator/=(const InfInt& rhs)
+{
+ //PROFINY_SCOPE
+ if (rhs == 0)
+ {
+#ifdef INFINT_USE_EXCEPTIONS
+ throw InfIntException("division by zero");
+#else
+ std::cerr << "Division by zero!" << std::endl;
+ return *this;
+#endif
+ }
+ InfInt R, D = (rhs.pos ? rhs : -rhs), N = (pos ? *this : -*this);
+ bool oldpos = pos;
+ std::fill(val.begin(), val.end(), 0);
+ for (int i = (int) N.val.size() - 1; i >= 0; --i)
+ {
+ R.val.insert(R.val.begin(), N.val[i]);
+ R.correct(true);
+ ELEM_TYPE cnt = dInR(R, D);
+ R -= D * cnt;
+ val[i] += cnt;
+ }
+ correct();
+ pos = (val.size() == 1 && val[0] == 0) ? true : (oldpos == rhs.pos);
+ return *this;
+}
+
+inline const InfInt& InfInt::operator%=(const InfInt& rhs)
+{
+ //PROFINY_SCOPE
+ if (rhs == 0)
+ {
+#ifdef INFINT_USE_EXCEPTIONS
+ throw InfIntException("division by zero");
+#else
+ std::cerr << "Division by zero!" << std::endl;
+ return *this;
+#endif
+ }
+ InfInt D = (rhs.pos ? rhs : -rhs), N = (pos ? *this : -*this);
+ bool oldpos = pos;
+ val.clear();
+ for (int i = (int) N.val.size() - 1; i >= 0; --i)
+ {
+ val.insert(val.begin(), N.val[i]);
+ correct(true);
+ *this -= D * dInR(*this, D);
+ }
+ correct();
+ pos = (val.size() == 1 && val[0] == 0) ? true : oldpos;
+ return *this;
+}
+
+inline const InfInt& InfInt::operator*=(ELEM_TYPE rhs)
+{
+ //PROFINY_SCOPE
+ ELEM_TYPE factor = rhs < 0 ? -rhs : rhs;
+ bool oldpos = pos;
+ multiplyByDigit(factor, val);
+ correct();
+ pos = (val.size() == 1 && val[0] == 0) ? true : (oldpos == (rhs >= 0));
+ return *this;
+}
+
+inline InfInt InfInt::operator-() const
+{
+ //PROFINY_SCOPE
+ InfInt result = *this;
+ result.pos = !pos;
+ return result;
+}
+
+inline InfInt InfInt::operator+(const InfInt& rhs) const
+{
+ //PROFINY_SCOPE
+ InfInt result;
+ result.val.resize(val.size() > rhs.val.size() ? val.size() : rhs.val.size(), 0);
+ for (size_t i = 0; i < val.size() || i < rhs.val.size(); ++i)
+ {
+ result.val[i] = (i < val.size() ? (pos ? val[i] : -val[i]) : 0) + (i < rhs.val.size() ? (rhs.pos ? rhs.val[i] : -rhs.val[i]) : 0);
+ }
+ result.correct();
+ return result;
+}
+
+inline InfInt InfInt::operator-(const InfInt& rhs) const
+{
+ //PROFINY_SCOPE
+ InfInt result;
+ result.val.resize(val.size() > rhs.val.size() ? val.size() : rhs.val.size(), 0);
+ for (size_t i = 0; i < val.size() || i < rhs.val.size(); ++i)
+ {
+ result.val[i] = (i < val.size() ? (pos ? val[i] : -val[i]) : 0) - (i < rhs.val.size() ? (rhs.pos ? rhs.val[i] : -rhs.val[i]) : 0);
+ }
+ result.correct();
+ return result;
+}
+
+inline InfInt InfInt::operator*(const InfInt& rhs) const
+{
+ //PROFINY_SCOPE
+ InfInt result;
+ result.val.resize(val.size() + rhs.val.size(), 0);
+ PRODUCT_TYPE carry = 0;
+ size_t digit = 0;
+ for (;; ++digit)
+ {
+ lldiv_t dt = my_lldiv(carry, BASE);
+ carry = dt.quot;
+ result.val[digit] = (ELEM_TYPE) dt.rem;
+
+ bool found = false;
+ for (size_t i = digit < rhs.val.size() ? 0 : digit - rhs.val.size() + 1; i < val.size() && i <= digit; ++i)
+ {
+ PRODUCT_TYPE pval = result.val[digit] + val[i] * (PRODUCT_TYPE) rhs.val[digit - i];
+ if (pval >= BASE || pval <= -BASE)
+ {
+ lldiv_t dt = my_lldiv(pval, BASE);
+ carry += dt.quot;
+ pval = dt.rem;
+ }
+ result.val[digit] = (ELEM_TYPE) pval;
+ found = true;
+ }
+ if (!found)
+ {
+ break;
+ }
+ }
+ for (; carry > 0; ++digit)
+ {
+ lldiv_t dt = my_lldiv(carry, BASE);
+ result.val[digit] = (ELEM_TYPE) dt.rem;
+ carry = dt.quot;
+ }
+ result.correct();
+ result.pos = (result.val.size() == 1 && result.val[0] == 0) ? true : (pos == rhs.pos);
+ return result;
+}
+
+inline InfInt InfInt::operator/(const InfInt& rhs) const
+{
+ //PROFINY_SCOPE
+ if (rhs == 0)
+ {
+#ifdef INFINT_USE_EXCEPTIONS
+ throw InfIntException("division by zero");
+#else
+ std::cerr << "Division by zero!" << std::endl;
+ return 0;
+#endif
+ }
+ InfInt Q, R, D = (rhs.pos ? rhs : -rhs), N = (pos ? *this : -*this);
+ Q.val.resize(N.val.size(), 0);
+ for (int i = (int) N.val.size() - 1; i >= 0; --i)
+ {
+ R.val.insert(R.val.begin(), N.val[i]);
+ R.correct(true);
+ ELEM_TYPE cnt = dInR(R, D);
+ R -= D * cnt;
+ Q.val[i] += cnt;
+ }
+ Q.correct();
+ Q.pos = (Q.val.size() == 1 && Q.val[0] == 0) ? true : (pos == rhs.pos);
+ return Q;
+}
+
+inline InfInt InfInt::operator%(const InfInt& rhs) const
+{
+ //PROFINY_SCOPE
+ if (rhs == 0)
+ {
+#ifdef INFINT_USE_EXCEPTIONS
+ throw InfIntException("division by zero");
+#else
+ std::cerr << "Division by zero!" << std::endl;
+ return 0;
+#endif
+ }
+ InfInt R, D = (rhs.pos ? rhs : -rhs), N = (pos ? *this : -*this);
+ for (int i = (int) N.val.size() - 1; i >= 0; --i)
+ {
+ R.val.insert(R.val.begin(), N.val[i]);
+ R.correct(true);
+ R -= D * dInR(R, D);
+ }
+ R.correct();
+ R.pos = (R.val.size() == 1 && R.val[0] == 0) ? true : pos;
+ return R;
+}
+
+inline InfInt InfInt::operator*(ELEM_TYPE rhs) const
+{
+ //PROFINY_SCOPE
+ InfInt result = *this;
+ ELEM_TYPE factor = rhs < 0 ? -rhs : rhs;
+ multiplyByDigit(factor, result.val);
+ result.correct();
+ result.pos = (result.val.size() == 1 && result.val[0] == 0) ? true : (pos == (rhs >= 0));
+ return result;
+}
+
+inline bool InfInt::operator==(const InfInt& rhs) const
+{
+ //PROFINY_SCOPE
+ if (pos != rhs.pos || val.size() != rhs.val.size())
+ {
+ return false;
+ }
+ for (int i = (int) val.size() - 1; i >= 0; --i)
+ {
+ if (val[i] != rhs.val[i])
+ {
+ return false;
+ }
+ }
+ return true;
+}
+
+inline bool InfInt::operator!=(const InfInt& rhs) const
+{
+ //PROFINY_SCOPE
+ if (pos != rhs.pos || val.size() != rhs.val.size())
+ {
+ return true;
+ }
+ for (int i = (int) val.size() - 1; i >= 0; --i)
+ {
+ if (val[i] != rhs.val[i])
+ {
+ return true;
+ }
+ }
+ return false;
+}
+
+inline bool InfInt::operator<(const InfInt& rhs) const
+{
+ //PROFINY_SCOPE
+ if (pos && !rhs.pos)
+ {
+ return false;
+ }
+ if (!pos && rhs.pos)
+ {
+ return true;
+ }
+ if (val.size() > rhs.val.size())
+ {
+ return pos ? false : true;
+ }
+ if (val.size() < rhs.val.size())
+ {
+ return pos ? true : false;
+ }
+ for (int i = (int) val.size() - 1; i >= 0; --i)
+ {
+ if (val[i] < rhs.val[i])
+ {
+ return pos ? true : false;
+ }
+ if (val[i] > rhs.val[i])
+ {
+ return pos ? false : true;
+ }
+ }
+ return false;
+}
+
+inline bool InfInt::operator<=(const InfInt& rhs) const
+{
+ //PROFINY_SCOPE
+ if (pos && !rhs.pos)
+ {
+ return false;
+ }
+ if (!pos && rhs.pos)
+ {
+ return true;
+ }
+ if (val.size() > rhs.val.size())
+ {
+ return pos ? false : true;
+ }
+ if (val.size() < rhs.val.size())
+ {
+ return pos ? true : false;
+ }
+ for (int i = (int) val.size() - 1; i >= 0; --i)
+ {
+ if (val[i] < rhs.val[i])
+ {
+ return pos ? true : false;
+ }
+ if (val[i] > rhs.val[i])
+ {
+ return pos ? false : true;
+ }
+ }
+ return true;
+}
+
+inline bool InfInt::operator>(const InfInt& rhs) const
+{
+ //PROFINY_SCOPE
+ if (pos && !rhs.pos)
+ {
+ return true;
+ }
+ if (!pos && rhs.pos)
+ {
+ return false;
+ }
+ if (val.size() > rhs.val.size())
+ {
+ return pos ? true : false;
+ }
+ if (val.size() < rhs.val.size())
+ {
+ return pos ? false : true;
+ }
+ for (int i = (int) val.size() - 1; i >= 0; --i)
+ {
+ if (val[i] < rhs.val[i])
+ {
+ return pos ? false : true;
+ }
+ if (val[i] > rhs.val[i])
+ {
+ return pos ? true : false;
+ }
+ }
+ return false;
+}
+
+inline bool InfInt::operator>=(const InfInt& rhs) const
+{
+ //PROFINY_SCOPE
+ if (pos && !rhs.pos)
+ {
+ return true;
+ }
+ if (!pos && rhs.pos)
+ {
+ return false;
+ }
+ if (val.size() > rhs.val.size())
+ {
+ return pos ? true : false;
+ }
+ if (val.size() < rhs.val.size())
+ {
+ return pos ? false : true;
+ }
+ for (int i = (int) val.size() - 1; i >= 0; --i)
+ {
+ if (val[i] < rhs.val[i])
+ {
+ return pos ? false : true;
+ }
+ if (val[i] > rhs.val[i])
+ {
+ return pos ? true : false;
+ }
+ }
+ return true;
+}
+
+inline void InfInt::optimizeSqrtSearchBounds(InfInt& lo, InfInt& hi) const
+{
+ //PROFINY_SCOPE
+ InfInt hdn = 1;
+ for (int i = (int) this->numberOfDigits() / 2; i >= 2; --i)
+ {
+ hdn *= 10;
+ }
+ if (lo < hdn)
+ {
+ lo = hdn;
+ }
+ hdn *= 100;
+ if (hi > hdn)
+ {
+ hi = hdn;
+ }
+}
+
+inline InfInt InfInt::intSqrt() const
+{
+ //PROFINY_SCOPE
+ if (*this <= 0)
+ {
+#ifdef INFINT_USE_EXCEPTIONS
+ throw InfIntException("intSqrt called for non-positive integer");
+#else
+ std::cerr << "intSqrt called for non-positive integer: " << *this << std::endl;
+ return 0;
+#endif
+ }
+ InfInt hi = *this / 2 + 1, lo = 0, mid, mid2;
+ optimizeSqrtSearchBounds(lo, hi);
+ do
+ {
+ mid = (hi + lo) / 2; // 8 factor
+ mid2 = mid * mid; // 1 factor
+ if (mid2 == *this)
+ {
+ lo = mid;
+ break;
+ }
+ else if (mid2 < *this)
+ {
+ lo = mid;
+ }
+ else
+ {
+ hi = mid;
+ }
+ } while (lo < hi - 1 && mid2 != *this);
+ return lo;
+}
+
+inline char InfInt::digitAt(size_t i) const
+{
+ //PROFINY_SCOPE
+ if (numberOfDigits() <= i)
+ {
+#ifdef INFINT_USE_EXCEPTIONS
+ throw InfIntException("invalid digit index");
+#else
+ std::cerr << "Invalid digit index: " << i << std::endl;
+ return -1;
+#endif
+ }
+ return (val[i / DIGIT_COUNT] / powersOfTen[i % DIGIT_COUNT]) % 10;
+}
+
+inline size_t InfInt::numberOfDigits() const
+{
+ //PROFINY_SCOPE
+ return (val.size() - 1) * DIGIT_COUNT +
+ (val.back() > 99999999 ? 9 : (val.back() > 9999999 ? 8 : (val.back() > 999999 ? 7 : (val.back() > 99999 ? 6 :
+ (val.back() > 9999 ? 5 : (val.back() > 999 ? 4 : (val.back() > 99 ? 3 : (val.back() > 9 ? 2 : 1))))))));
+}
+
+inline std::string InfInt::toString() const
+{
+ //PROFINY_SCOPE
+ std::ostringstream oss;
+ oss << *this;
+ return oss.str();
+}
+
+inline size_t InfInt::size() const
+{
+ //PROFINY_SCOPE
+ return val.size() * sizeof(ELEM_TYPE) + sizeof(bool);
+}
+
+inline int InfInt::toInt() const
+{
+ //PROFINY_SCOPE
+ if (*this > INT_MAX || *this < INT_MIN)
+ {
+#ifdef INFINT_USE_EXCEPTIONS
+ throw InfIntException("out of bounds");
+#else
+ std::cerr << "Out of INT bounds: " << *this << std::endl;
+#endif
+ }
+ int result = 0;
+ for (int i = (int) val.size() - 1; i >= 0; --i)
+ {
+ result = result * BASE + val[i];
+ }
+ return pos ? result : -result;
+}
+
+inline long InfInt::toLong() const
+{
+ //PROFINY_SCOPE
+ if (*this > LONG_MAX || *this < LONG_MIN)
+ {
+#ifdef INFINT_USE_EXCEPTIONS
+ throw InfIntException("out of bounds");
+#else
+ std::cerr << "Out of LONG bounds: " << *this << std::endl;
+#endif
+ }
+ long result = 0;
+ for (int i = (int) val.size() - 1; i >= 0; --i)
+ {
+ result = result * BASE + val[i];
+ }
+ return pos ? result : -result;
+}
+
+inline long long InfInt::toLongLong() const
+{
+ //PROFINY_SCOPE
+ if (*this > LONG_LONG_MAX || *this < LONG_LONG_MIN)
+ {
+#ifdef INFINT_USE_EXCEPTIONS
+ throw InfIntException("out of bounds");
+#else
+ std::cerr << "Out of LLONG bounds: " << *this << std::endl;
+#endif
+ }
+ long long result = 0;
+ for (int i = (int) val.size() - 1; i >= 0; --i)
+ {
+ result = result * BASE + val[i];
+ }
+ return pos ? result : -result;
+}
+
+inline unsigned int InfInt::toUnsignedInt() const
+{
+ //PROFINY_SCOPE
+ if (!pos || *this > UINT_MAX)
+ {
+#ifdef INFINT_USE_EXCEPTIONS
+ throw InfIntException("out of bounds");
+#else
+ std::cerr << "Out of UINT bounds: " << *this << std::endl;
+#endif
+ }
+ unsigned int result = 0;
+ for (int i = (int) val.size() - 1; i >= 0; --i)
+ {
+ result = result * BASE + val[i];
+ }
+ return result;
+}
+
+inline unsigned long InfInt::toUnsignedLong() const
+{
+ //PROFINY_SCOPE
+ if (!pos || *this > ULONG_MAX)
+ {
+#ifdef INFINT_USE_EXCEPTIONS
+ throw InfIntException("out of bounds");
+#else
+ std::cerr << "Out of ULONG bounds: " << *this << std::endl;
+#endif
+ }
+ unsigned long result = 0;
+ for (int i = (int) val.size() - 1; i >= 0; --i)
+ {
+ result = result * BASE + val[i];
+ }
+ return result;
+}
+
+inline unsigned long long InfInt::toUnsignedLongLong() const
+{
+ //PROFINY_SCOPE
+ if (!pos || *this > ULONG_LONG_MAX)
+ {
+#ifdef INFINT_USE_EXCEPTIONS
+ throw InfIntException("out of bounds");
+#else
+ std::cerr << "Out of ULLONG bounds: " << *this << std::endl;
+#endif
+ }
+ unsigned long long result = 0;
+ for (int i = (int) val.size() - 1; i >= 0; --i)
+ {
+ result = result * BASE + val[i];
+ }
+ return result;
+}
+
+inline void InfInt::truncateToBase()
+{
+ //PROFINY_SCOPE
+ for (size_t i = 0; i < val.size(); ++i) // truncate each
+ {
+ if (val[i] >= BASE || val[i] <= -BASE)
+ {
+ div_t dt = my_div(val[i], BASE);
+ val[i] = dt.rem;
+ if (i + 1 >= val.size())
+ {
+ val.push_back(dt.quot);
+ }
+ else
+ {
+ val[i + 1] += dt.quot;
+ }
+ }
+ }
+}
+
+inline bool InfInt::equalizeSigns()
+{
+ //PROFINY_SCOPE
+ bool isPositive = true;
+ int i = (int) ((val.size())) - 1;
+ for (; i >= 0; --i)
+ {
+ if (val[i] != 0)
+ {
+ isPositive = val[i--] > 0;
+ break;
+ }
+ }
+
+ if (isPositive)
+ {
+ for (; i >= 0; --i)
+ {
+ if (val[i] < 0)
+ {
+ int k = 0, index = i + 1;
+ for (; (size_t)(index) < val.size() && val[index] == 0; ++k, ++index); // count adjacent zeros on left
+ //if ((size_t)(index) < val.size() && val[index] > 0)
+ { // number on the left is positive
+ val[index] -= 1;
+ val[i] += BASE;
+ for (; k > 0; --k)
+ {
+ val[i + k] = UPPER_BOUND;
+ }
+ }
+ }
+ }
+ }
+ else
+ {
+ for (; i >= 0; --i)
+ {
+ if (val[i] > 0)
+ {
+ int k = 0, index = i + 1;
+ for (; (size_t)(index) < val.size() && val[index] == 0; ++k, ++index); // count adjacent zeros on right
+ //if ((size_t)(index) < val.size() && val[index] < 0)
+ { // number on the left is negative
+ val[index] += 1;
+ val[i] -= BASE;
+ for (; k > 0; --k)
+ {
+ val[i + k] = -UPPER_BOUND;
+ }
+ }
+ }
+ }
+ }
+
+ return isPositive;
+}
+
+inline void InfInt::removeLeadingZeros()
+{
+ //PROFINY_SCOPE
+ for (int i = (int) (val.size()) - 1; i > 0; --i) // remove leading 0's
+ {
+ if (val[i] != 0)
+ {
+ return;
+ }
+ else
+ {
+ val.erase(val.begin() + i);
+ }
+ }
+}
+
+inline void InfInt::correct(bool justCheckLeadingZeros, bool hasValidSign)
+{
+ //PROFINY_SCOPE
+ if (!justCheckLeadingZeros)
+ {
+ truncateToBase();
+
+ if (equalizeSigns())
+ {
+ pos = ((val.size() == 1 && val[0] == 0) || !hasValidSign) ? true : pos;
+ }
+ else
+ {
+ pos = hasValidSign ? !pos : false;
+ for (size_t i = 0; i < val.size(); ++i)
+ {
+ val[i] = abs(val[i]);
+ }
+ }
+ }
+
+ removeLeadingZeros();
+}
+
+inline void InfInt::fromString(const std::string& s)
+{
+ //PROFINY_SCOPE
+ pos = true;
+ val.clear();
+ val.reserve(s.size() / DIGIT_COUNT + 1);
+ int i = (int) s.size() - DIGIT_COUNT;
+ for (; i >= 0; i -= DIGIT_COUNT)
+ {
+ val.push_back(atoi(s.substr(i, DIGIT_COUNT).c_str()));
+ }
+ if (i > -DIGIT_COUNT)
+ {
+ std::string ss = s.substr(0, i + DIGIT_COUNT);
+ if (ss.size() == 1 && ss[0] == '-')
+ {
+ pos = false;
+ }
+ else
+ {
+ val.push_back(atoi(ss.c_str()));
+ }
+ }
+ if (val.back() < 0)
+ {
+ val.back() = -val.back();
+ pos = false;
+ }
+ correct(true);
+}
+
+inline ELEM_TYPE InfInt::dInR(const InfInt& R, const InfInt& D)
+{
+ //PROFINY_SCOPE
+ ELEM_TYPE min = 0, max = UPPER_BOUND;
+ while (max > min)
+ {
+ ELEM_TYPE avg = max + min;
+ div_t dt = my_div(avg, 2);
+ avg = dt.rem ? (dt.quot + 1) : dt.quot;
+ InfInt prod = D * avg;
+ if (R == prod)
+ {
+ return avg;
+ }
+ else if (R > prod)
+ {
+ min = avg;
+ }
+ else
+ {
+ max = avg - 1;
+ }
+ }
+ return min;
+}
+
+inline void InfInt::multiplyByDigit(ELEM_TYPE factor, std::vector<ELEM_TYPE>& val)
+{
+ //PROFINY_SCOPE
+ ELEM_TYPE carry = 0;
+ for (size_t i = 0; i < val.size(); ++i)
+ {
+ PRODUCT_TYPE pval = val[i] * (PRODUCT_TYPE) factor + carry;
+ if (pval >= BASE || pval <= -BASE)
+ {
+ lldiv_t dt = my_lldiv(pval, BASE);
+ carry = (ELEM_TYPE) dt.quot;
+ pval = dt.rem;
+ }
+ else
+ {
+ carry = 0;
+ }
+ val[i] = (ELEM_TYPE) pval;
+ }
+ if (carry > 0)
+ {
+ val.push_back(carry);
+ }
+}
+
+/**************************************************************/
+/******************** NON-MEMBER OPERATORS ********************/
+/**************************************************************/
+
+inline std::istream& operator>>(std::istream &s, InfInt &n)
+{
+ //PROFINY_SCOPE
+ std::string str;
+ s >> str;
+ n.fromString(str);
+ return s;
+}
+
+inline std::ostream& operator<<(std::ostream &s, const InfInt &n)
+{
+ //PROFINY_SCOPE
+ if (!n.pos)
+ {
+ s << '-';
+ }
+ bool first = true;
+ for (int i = (int) n.val.size() - 1; i >= 0; --i)
+ {
+ if (first)
+ {
+ s << n.val[i];
+ first = false;
+ }
+ else
+ {
+ s << std::setfill('0') << std::setw(DIGIT_COUNT) << n.val[i];
+ }
+ }
+ return s;
+}
+
+#endif
diff --git a/calc.cpp b/calc.cpp
@@ -1,3 +1,5 @@
+#include<limits.h>
+#include "InfInt.h"
#include <cstdio>
#include <deque>
#include <cassert>
@@ -7,17 +9,17 @@ using namespace std;
// http://math.stackexchange.com/q/2099305
-bool ok(deque<long long> &v) {
+bool ok(deque<InfInt> &v) {
for (unsigned int i = 0; i < v.size(); i++)
for (unsigned int j = i+1; j < v.size(); j++)
- if ((v[j] - v[i]) % v[i])
+ if (v[i] % (v[j] - v[i]) > 0)
return false;
return true;
}
// http://stackoverflow.com/a/4229930
-long long gcd(long long a, long long b)
+InfInt gcd(InfInt a, InfInt b)
{
for (;;)
{
@@ -29,28 +31,34 @@ long long gcd(long long a, long long b)
}
// http://stackoverflow.com/a/4229930
-long long lcm(long long a, long long b)
+InfInt lcm(InfInt a, InfInt b)
{
- long long temp = gcd(a, b);
+ InfInt temp = gcd(a, b);
- return temp ? (a / temp * b) : 0;
+ return temp > 0 ? (a / temp * b) : 0;
}
-int main() {
- deque<long long> v;
+int main(int argc, char **argv) {
+ deque<InfInt> v;
v.push_front(1);
- while (true) {
+ assert(argc == 2);
+ for (int iter = 0; iter < atoi(argv[1]); iter++) {
+ InfInt mygcd = 1;
+ for (auto x: v)
+ mygcd = lcm(mygcd, x);
+ v.push_front(0);
+ for (auto &x : v)
+ x += mygcd;
printf("%ld:", v.size());
for (auto x : v)
- printf(" %lld", x);
+ cout << " " << x;
printf("\n");
- // http://stackoverflow.com/a/4229930
- long long gcd = std::accumulate(v.begin(), v.end(), 1, lcm);
- v.push_front(0);
- for (auto &x : v)
- x += gcd;
+ if (!ok(v)) {
+ printf("PROBLEM\n");
+ return 1;
+ }
}
- assert(ok(v));
+ return 0;
}
