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