fork(1) download 
  1. #include <iostream>
  2. #include <vector>
  3. #include <sstream>
  4. #include <iomanip>
  5.  
  6. #include <limits.h>
  7. #include <stdlib.h>
  8.  
  9.  
  10. typedef int ELEM_TYPE;
  11. typedef long long PRODUCT_TYPE;
  12. static const ELEM_TYPE BASE = 1000000000;
  13. static const ELEM_TYPE UPPER_BOUND = 999999999;
  14. static const ELEM_TYPE DIGIT_COUNT = 9;
  15. static const int powersOfTen[] = { 1, 10, 100, 1000, 10000, 100000, 1000000, 10000000, 100000000 };
  16. class InfInt
  17. {
  18.     friend std::ostream& operator<<(std::ostream &s, const InfInt &n);
  19.     friend std::istream& operator>>(std::istream &s, InfInt &val);
  20.  
  21. public:
  22.     /* some constants */
  23.     static const InfInt zero;
  24.     static const InfInt one;
  25.     static const InfInt two;
  26.  
  27.     /* constructors */
  28.     InfInt();
  29.     InfInt(const char* c);
  30.     InfInt(const std::string& s);
  31.     InfInt(int l);
  32.     InfInt(long l);
  33.     InfInt(long long l);
  34.     InfInt(unsigned int l);
  35.     InfInt(unsigned long l);
  36.     InfInt(unsigned long long l);
  37.  
  38.     /* assignment operators */
  39.     const InfInt& operator=(const char* c);
  40.     const InfInt& operator=(const std::string& s);
  41.     const InfInt& operator=(int l);
  42.     const InfInt& operator=(long l);
  43.     const InfInt& operator=(long long l);
  44.     const InfInt& operator=(unsigned int l);
  45.     const InfInt& operator=(unsigned long l);
  46.     const InfInt& operator=(unsigned long long l);
  47.  
  48.     /* unary increment/decrement operators */
  49.     const InfInt& operator++();
  50.     const InfInt& operator--();
  51.     InfInt operator++(int);
  52.     InfInt operator--(int);
  53.  
  54.     /* operational assignments */
  55.     const InfInt& operator+=(const InfInt& rhs);
  56.     const InfInt& operator-=(const InfInt& rhs);
  57.     const InfInt& operator*=(const InfInt& rhs);
  58.     const InfInt& operator/=(const InfInt& rhs); // throw
  59.     const InfInt& operator%=(const InfInt& rhs); // throw
  60.     const InfInt& operator*=(ELEM_TYPE rhs);
  61.  
  62.     /* operations */
  63.     InfInt operator-() const;
  64.     InfInt operator+(const InfInt& rhs) const;
  65.     InfInt operator-(const InfInt& rhs) const;
  66.     InfInt operator*(const InfInt& rhs) const;
  67.     InfInt operator/(const InfInt& rhs) const; // throw
  68.     InfInt operator%(const InfInt& rhs) const; // throw
  69.     InfInt operator*(ELEM_TYPE rhs) const;
  70.  
  71.     /* relational operations */
  72.     bool operator==(const InfInt& rhs) const;
  73.     bool operator!=(const InfInt& rhs) const;
  74.     bool operator<(const InfInt& rhs) const;
  75.     bool operator<=(const InfInt& rhs) const;
  76.     bool operator>(const InfInt& rhs) const;
  77.     bool operator>=(const InfInt& rhs) const;
  78.  
  79.     /* integer square root */
  80.     InfInt intSqrt() const; // throw
  81.  
  82.     /* digit operations */
  83.     char digitAt(size_t i) const; // throw
  84.     size_t numberOfDigits() const;
  85.  
  86.     /* size in bytes */
  87.     size_t size() const;
  88.  
  89.     /* string conversion */
  90.     std::string toString() const;
  91.  
  92.     /* conversion to primitive types */
  93.     int toInt() const; // throw
  94.     long toLong() const; // throw
  95.     long long toLongLong() const; // throw
  96.     unsigned int toUnsignedInt() const; // throw
  97.     unsigned long toUnsignedLong() const; // throw
  98.     unsigned long long toUnsignedLongLong() const; // throw
  99.  
  100. private:
  101.     static ELEM_TYPE dInR(const InfInt& R, const InfInt& D);
  102.     static void multiplyByDigit(ELEM_TYPE factor, std::vector<ELEM_TYPE>& val);
  103.  
  104.     void correct(bool justCheckLeadingZeros = false, bool hasValidSign = false);
  105.     void fromString(const std::string& s);
  106.     void optimizeSqrtSearchBounds(InfInt& lo, InfInt& hi) const;
  107.     void truncateToBase();
  108.     bool equalizeSigns();
  109.     void removeLeadingZeros();
  110.  
  111.     std::vector<ELEM_TYPE> val; // number with base FACTOR
  112.     bool pos; // true if number is positive
  113. };
  114.  
  115. const InfInt InfInt::zero = 0;
  116. const InfInt InfInt::one = 1;
  117. const InfInt InfInt::two = 2;
  118.  
  119. inline InfInt::InfInt() : pos(true)
  120. {
  121.     val.push_back((ELEM_TYPE) 0);
  122. }
  123.  
  124. inline InfInt::InfInt(const char* c)
  125. {
  126.     fromString(c);
  127. }
  128.  
  129. inline InfInt::InfInt(const std::string& s)
  130. {
  131.     fromString(s);
  132. }
  133.  
  134. inline InfInt::InfInt(int l) : pos(l >= 0)
  135. {
  136.     if (!pos)
  137.     {
  138.         l = -l;
  139.     }
  140.     do
  141.     {
  142.         div_t dt = div(l, BASE);
  143.         val.push_back((ELEM_TYPE) dt.rem);
  144.         l = dt.quot;
  145.     } while (l > 0);
  146. }
  147.  
  148. inline InfInt::InfInt(long l) : pos(l >= 0)
  149. {
  150.     if (!pos)
  151.     {
  152.         l = -l;
  153.     }
  154.     do
  155.     {
  156.         ldiv_t dt = ldiv(l, BASE);
  157.         val.push_back((ELEM_TYPE) dt.rem);
  158.         l = dt.quot;
  159.     } while (l > 0);
  160. }
  161.  
  162. inline InfInt::InfInt(long long l) : pos(l >= 0)
  163. {
  164.     if (!pos)
  165.     {
  166.         l = -l;
  167.     }
  168.     do
  169.     {
  170.         val.push_back((ELEM_TYPE) (l % BASE));
  171.         l = l / BASE;
  172.     } while (l > 0);
  173. }
  174.  
  175. inline InfInt::InfInt(unsigned int l) : pos(true)
  176. {
  177.     do
  178.     {
  179.         val.push_back((ELEM_TYPE) (l % BASE));
  180.         l = l / BASE;
  181.     } while (l > 0);
  182. }
  183.  
  184. inline InfInt::InfInt(unsigned long l) : pos(true)
  185. {
  186.     do
  187.     {
  188.         val.push_back((ELEM_TYPE) (l % BASE));
  189.         l = l / BASE;
  190.     } while (l > 0);
  191. }
  192.  
  193. inline InfInt::InfInt(unsigned long long l) : pos(true)
  194. {
  195.     do
  196.     {
  197.         val.push_back((ELEM_TYPE) (l % BASE));
  198.         l = l / BASE;
  199.     } while (l > 0);
  200. }
  201.  
  202. inline const InfInt& InfInt::operator=(const char* c)
  203. {
  204.     fromString(c);
  205.     return *this;
  206. }
  207.  
  208. inline const InfInt& InfInt::operator=(const std::string& s)
  209. {
  210.     fromString(s);
  211.     return *this;
  212. }
  213.  
  214. inline const InfInt& InfInt::operator=(int l)
  215. {
  216.     pos = l >= 0;
  217.     val.clear();
  218.     if (!pos)
  219.     {
  220.         l = -l;
  221.     }
  222.     do
  223.     {
  224.         div_t dt = div(l, BASE);
  225.         val.push_back((ELEM_TYPE) dt.rem);
  226.         l = dt.quot;
  227.     } while (l > 0);
  228.     return *this;
  229. }
  230.  
  231. inline const InfInt& InfInt::operator=(long l)
  232. {
  233.     pos = l >= 0;
  234.     val.clear();
  235.     if (!pos)
  236.     {
  237.         l = -l;
  238.     }
  239.     do
  240.     {
  241.         ldiv_t dt = ldiv(l, BASE);
  242.         val.push_back((ELEM_TYPE) dt.rem);
  243.         l = dt.quot;
  244.     } while (l > 0);
  245.     return *this;
  246. }
  247.  
  248. inline const InfInt& InfInt::operator=(long long l)
  249. {
  250.     pos = l >= 0;
  251.     val.clear();
  252.     if (!pos)
  253.     {
  254.         l = -l;
  255.     }
  256.     do
  257.     {
  258.         val.push_back((ELEM_TYPE) (l % BASE));
  259.         l = l / BASE;
  260.     } while (l > 0);
  261.     return *this;
  262. }
  263.  
  264. inline const InfInt& InfInt::operator=(unsigned int l)
  265. {
  266.     pos = true;
  267.     val.clear();
  268.     do
  269.     {
  270.         val.push_back((ELEM_TYPE) (l % BASE));
  271.         l = l / BASE;
  272.     } while (l > 0);
  273.     return *this;
  274. }
  275.  
  276. inline const InfInt& InfInt::operator=(unsigned long l)
  277. {
  278.     pos = true;
  279.     val.clear();
  280.     do
  281.     {
  282.         val.push_back((ELEM_TYPE) (l % BASE));
  283.         l = l / BASE;
  284.     } while (l > 0);
  285.     return *this;
  286. }
  287.  
  288. inline const InfInt& InfInt::operator=(unsigned long long l)
  289. {
  290.     pos = true;
  291.     val.clear();
  292.     do
  293.     {
  294.         val.push_back((ELEM_TYPE) (l % BASE));
  295.         l = l / BASE;
  296.     } while (l > 0);
  297.     return *this;
  298. }
  299.  
  300. inline const InfInt& InfInt::operator++()
  301. {
  302.     val[0] += (pos ? 1 : -1);
  303.     this->correct(false, true);
  304.     return *this;
  305. }
  306.  
  307. inline const InfInt& InfInt::operator--()
  308. {
  309.     val[0] -= (pos ? 1 : -1);
  310.     this->correct(false, true);
  311.     return *this;
  312. }
  313.  
  314. inline InfInt InfInt::operator++(int)
  315. {
  316.     InfInt result = *this;
  317.     val[0] += (pos ? 1 : -1);
  318.     this->correct(false, true);
  319.     return result;
  320. }
  321.  
  322. inline InfInt InfInt::operator--(int)
  323. {
  324.     InfInt result = *this;
  325.     val[0] -= (pos ? 1 : -1);
  326.     this->correct(false, true);
  327.     return result;
  328. }
  329.  
  330. inline const InfInt& InfInt::operator+=(const InfInt& rhs)
  331. {
  332.     if (rhs.val.size() > val.size())
  333.     {
  334.         val.resize(rhs.val.size(), 0);
  335.     }
  336.     for (size_t i = 0; i < val.size(); ++i)
  337.     {
  338.         val[i] = (pos ? val[i] : -val[i]) + (i < rhs.val.size() ? (rhs.pos ? rhs.val[i] : -rhs.val[i]) : 0);
  339.     }
  340.     correct();
  341.     return *this;
  342. }
  343.  
  344. inline const InfInt& InfInt::operator-=(const InfInt& rhs)
  345. {
  346.     if (rhs.val.size() > val.size())
  347.     {
  348.         val.resize(rhs.val.size(), 0);
  349.     }
  350.     for (size_t i = 0; i < val.size(); ++i)
  351.     {
  352.         val[i] = (pos ? val[i] : -val[i]) - (i < rhs.val.size() ? (rhs.pos ? rhs.val[i] : -rhs.val[i]) : 0);
  353.     }
  354.     correct();
  355.     return *this;
  356. }
  357.  
  358. inline const InfInt& InfInt::operator*=(const InfInt& rhs)
  359. {
  360.     // TODO: optimize (do not use operator*)
  361.     *this = *this * rhs;
  362.     return *this;
  363. }
  364.  
  365. inline const InfInt& InfInt::operator/=(const InfInt& rhs)
  366. {
  367.     if (rhs == zero)
  368.     {
  369.         std::cerr << "Division by zero!" << std::endl;
  370.         return *this;
  371.     }
  372.     InfInt R, D = (rhs.pos ? rhs : -rhs), N = (pos ? *this : -*this);
  373.     bool oldpos = pos;
  374.     val.clear();
  375.     val.resize(N.val.size(), 0);
  376.     for (int i = (int) N.val.size() - 1; i >= 0; --i)
  377.     {
  378.         R.val.insert(R.val.begin(), (ELEM_TYPE) 0);
  379.         R.val[0] = N.val[i];
  380.         R.correct(true);
  381.         ELEM_TYPE cnt = dInR(R, D);
  382.         R -= D * cnt;
  383.         val[i] += cnt;
  384.     }
  385.     correct();
  386.     pos = (val.size() == 1 && val[0] == 0) ? true : (oldpos == rhs.pos);
  387.     return *this;
  388. }
  389.  
  390. inline const InfInt& InfInt::operator%=(const InfInt& rhs)
  391. {
  392.     if (rhs == zero)
  393.     {
  394.         std::cerr << "Division by zero!" << std::endl;
  395.         return zero;
  396.     }
  397.     InfInt D = (rhs.pos ? rhs : -rhs), N = (pos ? *this : -*this);
  398.     bool oldpos = pos;
  399.     val.clear();
  400.     for (int i = (int) N.val.size() - 1; i >= 0; --i)
  401.     {
  402.         val.insert(val.begin(), (ELEM_TYPE) 0);
  403.         val[0] = N.val[i];
  404.         correct(true);
  405.         *this -= D * dInR(*this, D);
  406.     }
  407.     correct();
  408.     pos = (val.size() == 1 && val[0] == 0) ? true : oldpos;
  409.     return *this;
  410. }
  411.  
  412. inline const InfInt& InfInt::operator*=(ELEM_TYPE rhs)
  413. {
  414.     ELEM_TYPE factor = rhs < 0 ? -rhs : rhs;
  415.     bool oldpos = pos;
  416.     multiplyByDigit(factor, val);
  417.     correct();
  418.     pos = (val.size() == 1 && val[0] == 0) ? true : (oldpos == (rhs >= 0));
  419.     return *this;
  420. }
  421.  
  422. inline InfInt InfInt::operator-() const
  423. {//PROFILED_SCOPE
  424.     InfInt result = *this;
  425.     result.pos = !pos;
  426.     return result;
  427. }
  428.  
  429. inline InfInt InfInt::operator+(const InfInt& rhs) const
  430. {//PROFILED_SCOPE
  431.     InfInt result;
  432.     result.val.resize(val.size() > rhs.val.size() ? val.size() : rhs.val.size(), 0);
  433.     for (size_t i = 0; i < val.size() || i < rhs.val.size(); ++i)
  434.     {
  435.         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);
  436.     }
  437.     result.correct();
  438.     return result;
  439. }
  440.  
  441. inline InfInt InfInt::operator-(const InfInt& rhs) const
  442. {//PROFILED_SCOPE
  443.     InfInt result;
  444.     result.val.resize(val.size() > rhs.val.size() ? val.size() : rhs.val.size(), 0);
  445.     for (size_t i = 0; i < val.size() || i < rhs.val.size(); ++i)
  446.     {
  447.         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);
  448.     }
  449.     result.correct();
  450.     return result;
  451. }
  452.  
  453. inline InfInt InfInt::operator*(const InfInt& rhs) const
  454. {//PROFILED_SCOPE
  455.     InfInt result;
  456.     result.val.resize(val.size() + rhs.val.size(), 0);
  457.     PRODUCT_TYPE carry = 0;
  458.     size_t digit = 0;
  459.     for (;; ++digit)
  460.     {//PROFILED_SCOPE
  461.         //result.val[digit] = (ELEM_TYPE) (carry % BASE);
  462.         //carry /= BASE;
  463.  
  464.         PRODUCT_TYPE oldcarry = carry;
  465.         carry /= BASE;
  466.         result.val[digit] = (ELEM_TYPE) (oldcarry - carry * BASE);
  467.  
  468.         bool found = false;
  469.         for (size_t i = digit < rhs.val.size() ? 0 : digit - rhs.val.size() + 1; i < val.size() && i <= digit; ++i)
  470.         {//PROFILED_SCOPE
  471.             PRODUCT_TYPE pval = result.val[digit] + val[i] * (PRODUCT_TYPE) rhs.val[digit - i];
  472.             if (pval >= BASE || pval <= -BASE)
  473.             {//PROFILED_SCOPE
  474.                 //carry += pval / BASE;
  475.                 //pval %= BASE;
  476.  
  477.                 PRODUCT_TYPE quot = pval / BASE;
  478.                 carry += quot;
  479.                 pval -= quot * BASE;
  480.             }
  481.             result.val[digit] = (ELEM_TYPE) pval;
  482.             found = true;
  483.         }
  484.         if (!found)
  485.         {//PROFILED_SCOPE
  486.             break;
  487.         }
  488.     }
  489.     for (; carry > 0; ++digit)
  490.     {//PROFILED_SCOPE
  491.         result.val[digit] = (ELEM_TYPE) (carry % BASE);
  492.         carry /= BASE;
  493.     }
  494.     result.correct();
  495.     result.pos = (result.val.size() == 1 && result.val[0] == 0) ? true : (pos == rhs.pos);
  496.     return result;
  497. }
  498.  
  499. inline InfInt InfInt::operator/(const InfInt& rhs) const
  500. {//PROFILED_SCOPE
  501.     if (rhs == zero)
  502.     {
  503.         std::cerr << "Division by zero!" << std::endl;
  504.         return zero;
  505.     }
  506.     InfInt Q, R, D = (rhs.pos ? rhs : -rhs), N = (pos ? *this : -*this);
  507.     Q.val.resize(N.val.size(), 0);
  508.     for (int i = (int) N.val.size() - 1; i >= 0; --i)
  509.     {//PROFILED_SCOPE
  510.         R.val.insert(R.val.begin(), (ELEM_TYPE) 0);
  511.         R.val[0] = N.val[i];
  512.         R.correct(true);
  513.         ELEM_TYPE cnt = dInR(R, D);
  514.         R -= D * cnt;
  515.         Q.val[i] += cnt;
  516.     }
  517.     Q.correct();
  518.     Q.pos = (Q.val.size() == 1 && Q.val[0] == 0) ? true : (pos == rhs.pos);
  519.     return Q;
  520. }
  521.  
  522. inline InfInt InfInt::operator%(const InfInt& rhs) const
  523. {//PROFILED_SCOPE
  524.     if (rhs == zero)
  525.     {
  526.         std::cerr << "Division by zero!" << std::endl;
  527.         return zero;
  528.     }
  529.     InfInt R, D = (rhs.pos ? rhs : -rhs), N = (pos ? *this : -*this);
  530.     for (int i = (int) N.val.size() - 1; i >= 0; --i)
  531.     {
  532.         R.val.insert(R.val.begin(), (ELEM_TYPE) 0);
  533.         R.val[0] = N.val[i];
  534.         R.correct(true);
  535.         R -= D * dInR(R, D);
  536.     }
  537.     R.correct();
  538.     R.pos = (R.val.size() == 1 && R.val[0] == 0) ? true : pos;
  539.     return R;
  540. }
  541.  
  542. inline InfInt InfInt::operator*(ELEM_TYPE rhs) const
  543. {//PROFILED_SCOPE
  544.     InfInt result = *this;
  545.     ELEM_TYPE factor = rhs < 0 ? -rhs : rhs;
  546.     multiplyByDigit(factor, result.val);
  547.     result.correct();
  548.     result.pos = (result.val.size() == 1 && result.val[0] == 0) ? true : (pos == (rhs >= 0));
  549.     return result;
  550. }
  551.  
  552. inline bool InfInt::operator==(const InfInt& rhs) const
  553. {//PROFILED_SCOPE
  554.     if (pos != rhs.pos || val.size() != rhs.val.size())
  555.     {
  556.         return false;
  557.     }
  558.     for (int i = (int) val.size() - 1; i >= 0; --i)
  559.     {
  560.         if (val[i] != rhs.val[i])
  561.         {
  562.             return false;
  563.         }
  564.     }
  565.     return true;
  566. }
  567.  
  568. inline bool InfInt::operator!=(const InfInt& rhs) const
  569. {//PROFILED_SCOPE
  570.     if (pos != rhs.pos || val.size() != rhs.val.size())
  571.     {
  572.         return true;
  573.     }
  574.     for (int i = (int) val.size() - 1; i >= 0; --i)
  575.     {
  576.         if (val[i] != rhs.val[i])
  577.         {
  578.             return true;
  579.         }
  580.     }
  581.     return false;
  582. }
  583.  
  584. inline bool InfInt::operator<(const InfInt& rhs) const
  585. {//PROFILED_SCOPE
  586.     if (pos && !rhs.pos)
  587.     {
  588.         return false;
  589.     }
  590.     if (!pos && rhs.pos)
  591.     {
  592.         return true;
  593.     }
  594.     if (val.size() > rhs.val.size())
  595.     {
  596.         return pos ? false : true;
  597.     }
  598.     if (val.size() < rhs.val.size())
  599.     {
  600.         return pos ? true : false;
  601.     }
  602.     for (int i = (int) val.size() - 1; i >= 0; --i)
  603.     {
  604.         if (val[i] < rhs.val[i])
  605.         {
  606.             return pos ? true : false;
  607.         }
  608.         if (val[i] > rhs.val[i])
  609.         {
  610.             return pos ? false : true;
  611.         }
  612.     }
  613.     return false;
  614. }
  615.  
  616. inline bool InfInt::operator<=(const InfInt& rhs) const
  617. {//PROFILED_SCOPE
  618.     if (pos && !rhs.pos)
  619.     {
  620.         return false;
  621.     }
  622.     if (!pos && rhs.pos)
  623.     {
  624.         return true;
  625.     }
  626.     if (val.size() > rhs.val.size())
  627.     {
  628.         return pos ? false : true;
  629.     }
  630.     if (val.size() < rhs.val.size())
  631.     {
  632.         return pos ? true : false;
  633.     }
  634.     for (int i = (int) val.size() - 1; i >= 0; --i)
  635.     {
  636.         if (val[i] < rhs.val[i])
  637.         {
  638.             return pos ? true : false;
  639.         }
  640.         if (val[i] > rhs.val[i])
  641.         {
  642.             return pos ? false : true;
  643.         }
  644.     }
  645.     return true;
  646. }
  647.  
  648. inline bool InfInt::operator>(const InfInt& rhs) const
  649. {//PROFILED_SCOPE
  650.     if (pos && !rhs.pos)
  651.     {
  652.         return true;
  653.     }
  654.     if (!pos && rhs.pos)
  655.     {
  656.         return false;
  657.     }
  658.     if (val.size() > rhs.val.size())
  659.     {
  660.         return pos ? true : false;
  661.     }
  662.     if (val.size() < rhs.val.size())
  663.     {
  664.         return pos ? false : true;
  665.     }
  666.     for (int i = (int) val.size() - 1; i >= 0; --i)
  667.     {
  668.         if (val[i] < rhs.val[i])
  669.         {
  670.             return pos ? false : true;
  671.         }
  672.         if (val[i] > rhs.val[i])
  673.         {
  674.             return pos ? true : false;
  675.         }
  676.     }
  677.     return false;
  678. }
  679.  
  680. inline bool InfInt::operator>=(const InfInt& rhs) const
  681. {//PROFILED_SCOPE
  682.     if (pos && !rhs.pos)
  683.     {
  684.         return true;
  685.     }
  686.     if (!pos && rhs.pos)
  687.     {
  688.         return false;
  689.     }
  690.     if (val.size() > rhs.val.size())
  691.     {
  692.         return pos ? true : false;
  693.     }
  694.     if (val.size() < rhs.val.size())
  695.     {
  696.         return pos ? false : true;
  697.     }
  698.     for (int i = (int) val.size() - 1; i >= 0; --i)
  699.     {
  700.         if (val[i] < rhs.val[i])
  701.         {
  702.             return pos ? false : true;
  703.         }
  704.         if (val[i] > rhs.val[i])
  705.         {
  706.             return pos ? true : false;
  707.         }
  708.     }
  709.     return true;
  710. }
  711.  
  712. inline void InfInt::optimizeSqrtSearchBounds(InfInt& lo, InfInt& hi) const
  713. {//PROFILED_SCOPE
  714.     InfInt hdn = one;
  715.     for (int i = (int) this->numberOfDigits() / 2; i >= 2; --i)
  716.     {
  717.         hdn *= 10;
  718.     }
  719.     if (lo < hdn)
  720.     {
  721.         lo = hdn;
  722.     }
  723.     hdn *= 100;
  724.     if (hi > hdn)
  725.     {
  726.         hi = hdn;
  727.     }
  728. }
  729.  
  730. inline InfInt InfInt::intSqrt() const
  731. {//PROFILED_SCOPE
  732.     if (*this <= zero)
  733.     {
  734.         std::cerr << "intSqrt called for non-positive integer: " << *this << std::endl;
  735.         return zero;
  736.     }
  737.     InfInt hi = *this / two + one, lo = zero, mid, mid2;
  738.     optimizeSqrtSearchBounds(lo, hi);
  739.     do
  740.     {
  741.         mid = (hi + lo) / two; // 8 factor
  742.         mid2 = mid * mid; // 1 factor
  743.         if (mid2 == *this)
  744.         {
  745.             lo = mid;
  746.             break;
  747.         }
  748.         else if (mid2 < *this)
  749.         {
  750.             lo = mid;
  751.         }
  752.         else
  753.         {
  754.             hi = mid;
  755.         }
  756.     } while (lo < hi - one && mid2 != *this);
  757.     return lo;
  758. }
  759.  
  760. inline char InfInt::digitAt(size_t i) const
  761. {//PROFILED_SCOPE
  762.     if (numberOfDigits() <= i)
  763.     {
  764.         std::cerr << "Invalid digit index: " << i << std::endl;
  765.         return -1;
  766.     }
  767.     return (val[i / DIGIT_COUNT] / powersOfTen[i % DIGIT_COUNT]) % 10;
  768. }
  769.  
  770. inline size_t InfInt::numberOfDigits() const
  771. {//PROFILED_SCOPE
  772.     return (val.size() - 1) * DIGIT_COUNT
  773.     + (val.back() > 99999999 ? 9 : (val.back() > 9999999 ? 8 : (val.back() > 999999 ? 7 : (val.back() > 99999 ? 6 :
  774.                                                                                            (val.back() > 9999 ? 5 : (val.back() > 999 ? 4 : (val.back() > 99 ? 3 : (val.back() > 9 ? 2 : 1))))))));
  775. }
  776.  
  777. inline std::string InfInt::toString() const
  778. {//PROFILED_SCOPE
  779.     std::ostringstream oss;
  780.     oss << *this;
  781.     return oss.str();
  782. }
  783.  
  784. inline size_t InfInt::size() const
  785. {//PROFILED_SCOPE
  786.     return val.size() * sizeof(ELEM_TYPE) + sizeof(bool);
  787. }
  788.  
  789. inline int InfInt::toInt() const
  790. {//PROFILED_SCOPE
  791.     if (*this > INT_MAX || *this < INT_MIN)
  792.     std::cerr << "Out of INT bounds: " << *this << std::endl;
  793.     int result = 0;
  794.     for (int i = (int) val.size() - 1; i >= 0; --i)
  795.     {
  796.         result = result * BASE + val[i];
  797.     }
  798.     return pos ? result : -result;
  799. }
  800.  
  801. inline long InfInt::toLong() const
  802. {//PROFILED_SCOPE
  803.     if (*this > LONG_MAX || *this < LONG_MIN)
  804.     std::cerr << "Out of LONG bounds: " << *this << std::endl;
  805.     long result = 0;
  806.     for (int i = (int) val.size() - 1; i >= 0; --i)
  807.     {
  808.         result = result * BASE + val[i];
  809.     }
  810.     return pos ? result : -result;
  811. }
  812.  
  813. inline long long InfInt::toLongLong() const
  814. {//PROFILED_SCOPE
  815.     if (*this > LONG_LONG_MAX || *this < LONG_LONG_MIN)
  816.     std::cerr << "Out of LLONG bounds: " << *this << std::endl;
  817.     long long result = 0;
  818.     for (int i = (int) val.size() - 1; i >= 0; --i)
  819.     {
  820.         result = result * BASE + val[i];
  821.     }
  822.     return pos ? result : -result;
  823. }
  824.  
  825. inline unsigned int InfInt::toUnsignedInt() const
  826. {//PROFILED_SCOPE
  827.     if (!pos || *this > UINT_MAX)
  828.     std::cerr << "Out of UINT bounds: " << *this << std::endl;
  829.     unsigned int result = 0;
  830.     for (int i = (int) val.size() - 1; i >= 0; --i)
  831.     {
  832.         result = result * BASE + val[i];
  833.     }
  834.     return result;
  835. }
  836.  
  837. inline unsigned long InfInt::toUnsignedLong() const
  838. {//PROFILED_SCOPE
  839.     if (!pos || *this > ULONG_MAX)
  840.     std::cerr << "Out of ULONG bounds: " << *this << std::endl;
  841.     unsigned long result = 0;
  842.     for (int i = (int) val.size() - 1; i >= 0; --i)
  843.     {
  844.         result = result * BASE + val[i];
  845.     }
  846.     return result;
  847. }
  848.  
  849. inline unsigned long long InfInt::toUnsignedLongLong() const
  850. {//PROFILED_SCOPE
  851.     if (!pos || *this > ULONG_LONG_MAX)
  852.     std::cerr << "Out of ULLONG bounds: " << *this << std::endl;
  853.     unsigned long long result = 0;
  854.     for (int i = (int) val.size() - 1; i >= 0; --i)
  855.     {
  856.         result = result * BASE + val[i];
  857.     }
  858.     return result;
  859. }
  860.  
  861. inline void InfInt::truncateToBase()
  862. {//PROFILED_SCOPE
  863.     for (size_t i = 0; i < val.size(); ++i) // truncate each
  864.     {
  865.         if (val[i] >= BASE || val[i] <= -BASE)
  866.         {//PROFILED_SCOPE
  867.             div_t dt = div(val[i], BASE);
  868.             val[i] = dt.rem;
  869.             if (i + 1 >= val.size())
  870.             {//PROFILED_SCOPE
  871.                 val.push_back(dt.quot);
  872.             }
  873.             else
  874.             {//PROFILED_SCOPE
  875.                 val[i + 1] += dt.quot;
  876.             }
  877.         }
  878.     }
  879. }
  880.  
  881. inline bool InfInt::equalizeSigns()
  882. {//PROFILED_SCOPE
  883.     bool isPositive = true;
  884.     int i = (int) ((val.size())) - 1;
  885.     for (; i >= 0; --i)
  886.     {
  887.         if (val[i] != 0)
  888.         {
  889.             isPositive = val[i--] > 0;
  890.             break;
  891.         }
  892.     }
  893.  
  894.     if (isPositive)
  895.     {
  896.         for (; i >= 0; --i)
  897.         {
  898.             if (val[i] < 0)
  899.             {
  900.                 int k = 0, index = i + 1;
  901.                 for (; (size_t)(index) < val.size() && val[index] == 0; ++k, ++index); // count adjacent zeros on left
  902.                 //if ((size_t)(index) < val.size() && val[index] > 0)
  903.                 { // number on the left is positive
  904.                     val[index] -= 1;
  905.                     val[i] += BASE;
  906.                     for (; k > 0; --k)
  907.                     {
  908.                         val[i + k] = UPPER_BOUND;
  909.                     }
  910.                 }
  911.             }
  912.         }
  913.     }
  914.     else
  915.     {
  916.         for (; i >= 0; --i)
  917.         {
  918.             if (val[i] > 0)
  919.             {
  920.                 int k = 0, index = i + 1;
  921.                 for (; (size_t)(index) < val.size() && val[index] == 0; ++k, ++index); // count adjacent zeros on right
  922.                 //if ((size_t)(index) < val.size() && val[index] < 0)
  923.                 { // number on the left is negative
  924.                     val[index] += 1;
  925.                     val[i] -= BASE;
  926.                     for (; k > 0; --k)
  927.                     {
  928.                         val[i + k] = -UPPER_BOUND;
  929.                     }
  930.                 }
  931.             }
  932.         }
  933.     }
  934.  
  935.     return isPositive;
  936. }
  937.  
  938. inline void InfInt::removeLeadingZeros()
  939. {//PROFILED_SCOPE
  940.     for (int i = (int) (val.size()) - 1; i > 0; --i) // remove leading 0's
  941.     {
  942.         if (val[i] != 0)
  943.         {
  944.             return;
  945.         }
  946.         else
  947.         {
  948.             val.erase(val.begin() + i);
  949.         }
  950.     }
  951. }
  952.  
  953. inline void InfInt::correct(bool justCheckLeadingZeros, bool hasValidSign)
  954. {//PROFILED_SCOPE
  955.     if (!justCheckLeadingZeros)
  956.     {
  957.         truncateToBase();
  958.  
  959.         if (equalizeSigns())
  960.         {
  961.             pos = ((val.size() == 1 && val[0] == 0) || !hasValidSign) ? true : pos;
  962.         }
  963.         else
  964.         {
  965.             pos = hasValidSign ? !pos : false;
  966.             for (size_t i = 0; i < val.size(); ++i)
  967.             {
  968.                 val[i] = abs(val[i]);
  969.             }
  970.         }
  971.     }
  972.  
  973.     removeLeadingZeros();
  974. }
  975.  
  976. inline void InfInt::fromString(const std::string& s)
  977. {//PROFILED_SCOPE
  978.     pos = true;
  979.     val.clear();
  980.     // TODO use resize
  981.     val.reserve(s.size() / DIGIT_COUNT + 1);
  982.     int i = (int) s.size() - DIGIT_COUNT;
  983.     for (; i >= 0; i -= DIGIT_COUNT)
  984.     {
  985.         val.push_back(atoi(s.substr(i, DIGIT_COUNT).c_str()));
  986.     }
  987.     if (i > -DIGIT_COUNT)
  988.     {
  989.         std::string ss = s.substr(0, i + DIGIT_COUNT);
  990.         if (ss.size() == 1 && ss[0] == '-')
  991.         {
  992.             pos = false;
  993.         }
  994.         else
  995.         {
  996.             val.push_back(atoi(ss.c_str()));
  997.         }
  998.     }
  999.     if (val.back() < 0)
  1000.     {
  1001.         val.back() = -val.back();
  1002.         pos = false;
  1003.     }
  1004.     correct(true);
  1005. }
  1006.  
  1007. inline ELEM_TYPE InfInt::dInR(const InfInt& R, const InfInt& D)
  1008. {//PROFILED_SCOPE
  1009.     ELEM_TYPE min = 0, max = UPPER_BOUND;
  1010.     while (max - min > 0)
  1011.     {
  1012.         ELEM_TYPE avg = max + min;
  1013.         //div_t dt = div(avg, 2);
  1014.         //avg = dt.rem ? (dt.quot + 1) : dt.quot;
  1015.         ELEM_TYPE havg = avg / 2;
  1016.         avg = (avg - havg * 2) ? (havg + 1) : havg;
  1017.         InfInt prod = D * avg;
  1018.         if (R == prod)
  1019.         {//PROFILED_SCOPE
  1020.             return avg;
  1021.         }
  1022.         else if (R > prod)
  1023.         {//PROFILED_SCOPE
  1024.             min = avg;
  1025.         }
  1026.         else
  1027.         {//PROFILED_SCOPE
  1028.             max = avg - 1;
  1029.         }
  1030.     }
  1031.     return min;
  1032. }
  1033.  
  1034. inline void InfInt::multiplyByDigit(ELEM_TYPE factor, std::vector<ELEM_TYPE>& val)
  1035. {//PROFILED_SCOPE
  1036.     ELEM_TYPE carry = 0;
  1037.     for (size_t i = 0; i < val.size(); ++i)
  1038.     {
  1039.         PRODUCT_TYPE pval = val[i] * (PRODUCT_TYPE) factor + carry;
  1040.         if (pval >= BASE || pval <= -BASE)
  1041.         {
  1042.             //carry = (ELEM_TYPE) (pval / BASE);
  1043.             //pval %= BASE;
  1044.  
  1045.             carry = (ELEM_TYPE) (pval / BASE);
  1046.             pval -= carry * BASE;
  1047.         }
  1048.         else
  1049.         {
  1050.             carry = 0;
  1051.         }
  1052.         val[i] = (ELEM_TYPE) pval;
  1053.     }
  1054.     if (carry > 0)
  1055.     {
  1056.         val.push_back(carry);
  1057.     }
  1058. }
  1059.  
  1060. /**************************************************************/
  1061. /******************** NON-MEMBER OPERATORS ********************/
  1062. /**************************************************************/
  1063.  
  1064. inline std::istream& operator>>(std::istream &s, InfInt &n)
  1065. {//PROFILED_SCOPE
  1066.     std::string str;
  1067.     s >> str;
  1068.     n.fromString(str);
  1069.     return s;
  1070. }
  1071.  
  1072. inline std::ostream& operator<<(std::ostream &s, const InfInt &n)
  1073. {//PROFILED_SCOPE
  1074.     if (!n.pos)
  1075.     {
  1076.         s << '-';
  1077.     }
  1078.     bool first = true;
  1079.     for (int i = (int) n.val.size() - 1; i >= 0; --i)
  1080.     {
  1081.         if (first)
  1082.         {
  1083.             s << n.val[i];
  1084.             first = false;
  1085.         }
  1086.         else
  1087.         {
  1088.             s << std::setfill('0') << std::setw(DIGIT_COUNT) << n.val[i];
  1089.         }
  1090.     }
  1091.     return s;
  1092. }
  1093.  
  1094. using namespace std;
  1095. int main(){
  1096.     int a;
  1097.     cin >> a;
  1098.     InfInt x = 1, kg;
  1099.     for (int cont = 0; cont < a; cont++) {
  1100.         x *= 2;
  1101.     }
  1102.     kg = x / 12000;
  1103.     cout << kg << " kg\n";
  1104. }
  1105.  
Success #stdin #stdout 0s 3476KB
comments (?)
stdin 
64
stdout 
1537228672809129 kg
https://ideone.com/3WEEFC
language:
C++14 (gcc 8.3)
created:
8 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!