fork download 
  1. #ifndef DODECAHEDRON_BIGINT_H_
  2. #define DODECAHEDRON_BIGINT_H_
  3.  
  4. #include <vector>
  5. #include <iostream>
  6. #include <map>
  7. #include <string>
  8. #include <sstream>
  9.  
  10. namespace Dodecahedron
  11. {
  12. class Bigint
  13. {
  14. private:
  15.     std::vector<int> number;
  16.     bool positive;
  17.     int base;
  18.     unsigned int skip;
  19.     static const int default_base=1000000000;
  20.  
  21. public:
  22.     //Constructors
  23.     Bigint();
  24.     Bigint(long long);
  25.     Bigint(std::string);
  26.     Bigint(const Bigint& b);
  27.  
  28.     //Adding
  29.     Bigint operator+(Bigint const &) const;
  30.     Bigint &operator+=(Bigint const &);
  31.     Bigint operator+(long long const &) const;
  32.     Bigint &operator+=(long long);
  33.  
  34.     //Subtraction
  35.     Bigint operator-(Bigint const &) const;
  36.     Bigint &operator-=(Bigint const &);
  37.  
  38.     //Multiplication
  39.     Bigint operator*(Bigint const &);
  40.     Bigint &operator*=(Bigint const &);
  41.     Bigint operator*(long long const &);
  42.     Bigint &operator*=(int const &);
  43.  
  44.     //Compare
  45.     bool operator<(const Bigint &) const;
  46.     bool operator>(const Bigint &) const;
  47.     bool operator<=(const Bigint &) const;
  48.     bool operator>=(const Bigint &) const;
  49.     bool operator==(const Bigint &) const;
  50.     bool operator!=(const Bigint &) const;
  51.  
  52.     //Allocation
  53.     Bigint operator=(const long long &);
  54.  
  55.     //Access
  56.     int operator[](int const &);
  57.  
  58.     //Input&Output
  59.     friend std::istream &operator>>(std::istream &, Bigint &);
  60.     friend std::ostream &operator<<(std::ostream &, Bigint const &);
  61.  
  62.     //Helpers
  63.     void clear();
  64.     Bigint &abs();
  65.  
  66.     //Power
  67.     Bigint &pow(int const &);
  68.  
  69.     //Trivia
  70.     int digits() const;
  71.     int trailing_zeros() const;
  72. private:
  73.     int segment_length(int) const;
  74.     Bigint pow(int const &, std::map<int, Bigint> &);
  75.     int compare(Bigint const &) const; //0 a == b, -1 a < b, 1 a > b
  76. };
  77.  
  78. Bigint abs(Bigint);
  79. std::string to_string(Bigint const &);
  80. Bigint factorial(int);
  81. }
  82.  
  83. #endif
  84.  
  85. namespace Dodecahedron
  86. {
  87.  
  88. //Constructor
  89. Bigint::Bigint()
  90. {
  91.     positive = true;
  92.     base = Bigint::default_base;
  93.     skip = 0;
  94. }
  95. Bigint::Bigint(const Bigint &b)
  96.         : number(b.number),
  97.           positive(b.positive),
  98.           base(b.base),
  99.           skip(b.skip) { }
  100. Bigint::Bigint(long long value)
  101. {
  102.     base = Bigint::default_base;
  103.     skip = 0;
  104.     if (value < 0) {
  105.         positive = false;
  106.         value *= -1;
  107.     } else {
  108.         positive = true;
  109.     }
  110.  
  111.     while (value) {
  112.         number.push_back((int) (value % base));
  113.         value /= base;
  114.     }
  115. }
  116.  
  117. Bigint::Bigint(std::string stringInteger)
  118. {
  119.     int size = stringInteger.length();
  120.  
  121.     base = Bigint::default_base;
  122.     skip = 0;
  123.     positive = (stringInteger[0] != '-');
  124.  
  125.     while (true) {
  126.         if (size <= 0) break;
  127.         if (!positive && size <= 1) break;
  128.  
  129.         int length = 0;
  130.         int num = 0;
  131.         int prefix = 1;
  132.         for (int i(size - 1); i >= 0 && i >= size - 9; --i) {
  133.             if (stringInteger[i] < '0' || stringInteger[i] > '9') break;
  134.             num += (stringInteger[i] - '0') * prefix;
  135.             prefix *= 10;
  136.             ++length;
  137.         }
  138.         number.push_back(num);
  139.         size -= length;
  140.     }
  141. }
  142.  
  143. //Adding
  144. Bigint Bigint::operator+(Bigint const &b) const
  145. {
  146.     Bigint c = *this;
  147.     c += b;
  148.  
  149.     return c;
  150. }
  151.  
  152. Bigint &Bigint::operator+=(Bigint const &b)
  153. {
  154.     if (!b.positive) {
  155.         return *this -= b;
  156.     }
  157.     std::vector<int>::iterator
  158.         it1 = number.begin();
  159.     std::vector<int>::const_iterator
  160.         it2 = b.number.begin();
  161.     int sum = 0;
  162.     while (it1 != number.end() || it2 != b.number.end()) {
  163.         if (it1 != number.end()) {
  164.             sum += *it1;
  165.         } else {
  166.             number.push_back(0);
  167.             it1 = number.end()-1;
  168.         }
  169.         if (it2 != b.number.end()) {
  170.             sum += *it2;
  171.             ++it2;
  172.         }
  173.         *it1 = sum % base;
  174.         ++it1;
  175.         sum /= base;
  176.     }
  177.     if (sum) number.push_back(1);
  178.  
  179.     return *this;
  180. }
  181.  
  182. Bigint Bigint::operator+(long long const &b) const
  183. {
  184.     Bigint c = *this;
  185.     c += b;
  186.  
  187.     return c;
  188. }
  189.  
  190. Bigint &Bigint::operator+=(long long b)
  191. {
  192.     std::vector<int>::iterator it = number.begin();
  193.     if (skip > number.size()) {
  194.         number.insert(number.end(), skip - number.size(), 0);
  195.     }
  196.     it += skip;
  197.     bool initial_flag=true;
  198.     while (b || initial_flag) {
  199.         initial_flag=false;
  200.         if (it != number.end()) {
  201.             *it += b % base;
  202.             b /= base;
  203.             b += *it / base;
  204.             *it %= base;
  205.             ++it;
  206.         } else {
  207.             number.push_back(0);
  208.             it = number.end() - 1;
  209.         }
  210.     }
  211.  
  212.     return *this;
  213. }
  214.  
  215. //Subtraction
  216. Bigint Bigint::operator-(Bigint const &b) const
  217. {
  218.     Bigint c = *this;
  219.     c -= b;
  220.  
  221.     return c;
  222. }
  223.  
  224. Bigint &Bigint::operator-=(Bigint const &b)
  225. {
  226.     std::vector<int>::iterator
  227.         it1 = number.begin();
  228.     std::vector<int>::const_iterator
  229.         it2 = b.number.begin();
  230.     int dif = 0;
  231.     while (it1 != number.end() || it2 != b.number.end()) {
  232.         if (it1 != number.end()) {
  233.             dif += *it1;
  234.             ++it1;
  235.         }
  236.         if (it2 != b.number.end()) {
  237.             dif -= *it2;
  238.             ++it2;
  239.         }
  240.         if (dif < 0) {
  241.             *(it1 - 1) = dif + base;
  242.             dif = -1;
  243.         } else {
  244.             *(it1 - 1) = dif % base;
  245.             dif /= base;
  246.         }
  247.     }
  248.     if (dif < 0) positive = false;
  249.  
  250.     if (number.size() > 1)
  251.     {
  252.         do
  253.         {
  254.             it1 = number.end() - 1;
  255.             if (*it1 == 0) number.pop_back();
  256.             else break;
  257.         } while (number.size() > 1);
  258.     }
  259.  
  260.     return *this;
  261. }
  262.  
  263. //Multiplication
  264. Bigint Bigint::operator*(Bigint const &b)
  265. {
  266.     if (b.number.size() == 1) return *this *= b.number[0];
  267.     std::vector<int>::iterator it1;
  268.     std::vector<int>::const_iterator it2;
  269.     Bigint c;
  270.     for (it1 = number.begin(); it1 != number.end(); ++it1) {
  271.         for (it2 = b.number.begin(); it2 != b.number.end(); ++it2) {
  272.             c.skip = (unsigned int) (it1 - number.begin()) + (it2 - b.number.begin()); //TODO
  273.             c += (long long) (*it1) * (*it2);
  274.         }
  275.     }
  276.     c.skip = 0;
  277.  
  278.     return c;
  279. }
  280.  
  281. Bigint &Bigint::operator*=(Bigint const &b)
  282. {
  283.     *this = *this * b;
  284.  
  285.     return *this;
  286. }
  287.  
  288. Bigint Bigint::operator*(long long const &b)
  289. {
  290.     Bigint c = *this;
  291.     c *= b;
  292.  
  293.     return c;
  294. }
  295.  
  296. Bigint &Bigint::operator*=(int const &b)
  297. {
  298.     std::vector<int>::iterator it = number.begin();
  299.     long long sum = 0;
  300.     while (it != number.end()) {
  301.         sum += (long long) (*it) * b;
  302.         *it = (int) (sum % base);
  303.         sum /= base;
  304.         ++it;
  305.     }
  306.     if (sum) number.push_back((int) sum);
  307.  
  308.     return *this;
  309. }
  310.  
  311. //Power
  312. Bigint Bigint::pow(int const &power, std::map<int, Bigint> &lookup)
  313. {
  314.     if (power == 1) return *this;
  315.     if (lookup.count(power)) return lookup[power];
  316.  
  317.     int closestPower = 1;
  318.     while (closestPower < power) closestPower <<= 1;
  319.     closestPower >>= 1;
  320.  
  321.     if (power == closestPower) lookup[power] = pow(power / 2, lookup) * pow(power / 2, lookup);
  322.     else lookup[power] = pow(closestPower, lookup) * pow(power - closestPower, lookup);
  323.  
  324.     return lookup[power];
  325. }
  326.  
  327. Bigint &Bigint::pow(int const &power)
  328. {
  329.     std::map<int, Bigint> lookup;
  330.     if (power % 2 == 0 && !positive) {
  331.         positive = true;
  332.     }
  333.     *this = pow(power, lookup);
  334.  
  335.     return *this;
  336. }
  337.  
  338. //Compare
  339. int Bigint::compare(const Bigint &a) const //0 this == a || -1 this < a || 1 this > a
  340. {
  341.     if (positive && !a.positive) return 1;
  342.     if (!positive && a.positive) return -1;
  343.  
  344.     int check = 1;
  345.     if (!positive && !a.positive) check = -1;
  346.  
  347.     if (number.size() < a.number.size()) return -1 * check;
  348.     if (number.size() > a.number.size()) return check;
  349.     for (size_t i(number.size()); i > 0; --i) {
  350.         if (number[i-1] < a.number[i-1]) return -1 * check;
  351.         if (number[i-1] > a.number[i-1]) return check;
  352.     }
  353.  
  354.     return 0; // ==
  355. }
  356.  
  357. bool Bigint::operator<(Bigint const &b) const
  358. {
  359.     return compare(b) == -1;
  360. }
  361.  
  362. bool Bigint::operator<=(const Bigint &b) const
  363. {
  364.     int compared = compare(b);
  365.  
  366.     return compared == 0 || compared == -1;
  367. }
  368.  
  369. bool Bigint::operator>(const Bigint &b) const
  370. {
  371.     return compare(b) == 1;
  372. }
  373.  
  374. bool Bigint::operator>=(const Bigint &b) const
  375. {
  376.     int compared = compare(b);
  377.  
  378.     return compared == 0 || compared == 1;
  379. }
  380.  
  381. bool Bigint::operator==(Bigint const &b) const
  382. {
  383.     return compare(b) == 0;
  384. }
  385.  
  386. bool Bigint::operator!=(Bigint const &b) const
  387. {
  388.     return ! (*this == b);
  389. }
  390.  
  391. //Allocation
  392. Bigint Bigint::operator=(const long long &a)
  393. {
  394.     number.clear();
  395.     long long t = a;
  396.     do {
  397.         number.push_back((int) (t % base));
  398.         t /= base;
  399.     } while (t != 0);
  400.  
  401.     return *this;
  402. }
  403.  
  404. //Access
  405. int Bigint::operator[](int const &b)
  406. {
  407.     return to_string(*this)[b] - '0';
  408. }
  409.  
  410. //Trivia
  411. int Bigint::digits() const
  412. {
  413.     int segments = number.size();
  414.  
  415.     if (segments == 0) return 0;
  416.  
  417.     int digits = 9 * (segments - 1);
  418.     digits += segment_length(number.back());
  419.  
  420.     return digits;
  421. }
  422.  
  423. int Bigint::trailing_zeros() const
  424. {
  425.     if (number.empty() || (number.size() == 1 && number[0] == 0)) return 1;
  426.  
  427.     int zeros = 0;
  428.     std::vector<int>::const_iterator it = number.begin();
  429.     if (number.size() > 1) {
  430.         for (; it != number.end() - 1 && *it == 0; ++it) {
  431.             zeros += 9;
  432.         }
  433.     }
  434.     int a = *it;
  435.     while (a % 10 == 0 && a) {
  436.         ++zeros;
  437.         a /= 10;
  438.     }
  439.  
  440.     return zeros;
  441. }
  442.  
  443. //Helpers
  444. void Bigint::clear()
  445. {
  446.     number.clear();
  447.     positive = true;
  448.     skip = 0;
  449. }
  450.  
  451. Bigint &Bigint::abs()
  452. {
  453.     positive = true;
  454.  
  455.     return *this;
  456. }
  457.  
  458. //Input&Output
  459. std::ostream &operator<<(std::ostream &out, Bigint const &a)
  460. {
  461.     if (!a.number.size()) return out << 0;
  462.     int i = a.number.size() - 1;
  463.     for (; i>=0 && a.number[i] == 0; --i);
  464.  
  465.     if (i == -1) return out << 0;
  466.     if (!a.positive) out << '-';
  467.  
  468.     std::vector<int>::const_reverse_iterator it = a.number.rbegin() + (a.number.size() - i - 1);
  469.  
  470.     out << *it++;
  471.     for (; it != a.number.rend(); ++it) {
  472.         for (int i(0), len = a.segment_length(*it); i < 9 - len; ++i) out << '0';
  473.         if (*it) out << *it;
  474.     }
  475.  
  476.     return out;
  477. }
  478.  
  479. std::istream &operator>>(std::istream &in, Bigint &a)
  480. {
  481.     std::string str;
  482.     in >> str;
  483.  
  484.     a = str;
  485.  
  486.     return in;
  487. }
  488.  
  489. int Bigint::segment_length(int segment) const
  490. {
  491.     int length = 0;
  492.     while (segment) {
  493.         segment /= 10;
  494.         ++length;
  495.     }
  496.  
  497.     return length;
  498. }
  499.  
  500. Bigint abs(Bigint value)
  501. {
  502.     return value.abs();
  503. }
  504.  
  505. std::string to_string(Bigint const &value)
  506. {
  507.     std::ostringstream stream;
  508.     stream << value;
  509.  
  510.     return stream.str();
  511. }
  512.  
  513. Bigint factorial(int n)
  514. {
  515.     Bigint result = 1;
  516.     if (n % 2) {
  517.         result = n;
  518.         --n;
  519.     }
  520.     int last = 0;
  521.     for (; n >= 2; n -= 2) {
  522.         result *= n + last;
  523.         last += n;
  524.     }
  525.  
  526.     return result;
  527. }
  528.  
  529. }
  530.  
  531.  
  532. int main() {
  533. 	Dodecahedron::Bigint a("a");
  534. 	std::cout << a;	
  535. }
Time limit exceeded #stdin #stdout 5s 4563468KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/D5RwNF
language:
C++14 (gcc 8.3)
created:
4 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!