API tools faq
paste
EntropyIncreaser

Big Number

EntropyIncreaser
Aug 29th, 2018
400
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 13.98 KB | None | 0 0
raw download clone embed print report
  1. #include <cstdio>
  2. #include <cstring>
  3.  
  4. #include <algorithm>
  5. #include <iostream>
  6. #include <complex>
  7. #include <string>
  8. #include <vector>
  9.  
  10. #define LOG(FMT...) fprintf(stderr, FMT)
  11.  
  12. #define DECL_IOSTREAM(T) istream& operator>>(istream& is, T& x) { \
  13.     string s; \
  14.     is >> s; \
  15.     x = s; \
  16.     return is; \
  17. } \
  18. ostream& operator<<(ostream& os, const T& x) { \
  19.     return os << x.toString(); \
  20. }
  21.  
  22. using namespace std;
  23.  
  24. typedef long long ll;
  25. typedef complex<double> cd;
  26.  
  27. const int BASE = 5, MOD = 100000, LGM = 17;
  28. const double PI = 3.1415926535897932384626;
  29.  
  30. class UnsignedDigit;
  31.  
  32. namespace DivHelper { UnsignedDigit quasiInv(const UnsignedDigit& v); }
  33.  
  34. class UnsignedDigit {
  35. private:
  36.     vector<int> digits;
  37.  
  38. public:
  39.     UnsignedDigit() : digits(1) {}
  40.  
  41.     UnsignedDigit(const vector<int>& digits);
  42.  
  43.     UnsignedDigit(ll x);
  44.     UnsignedDigit(string str);
  45.  
  46.     int size() const { return digits.size(); }
  47.     bool zero() const { return digits.size() == 1 && digits[0] == 0; }
  48.  
  49.     bool operator<(const UnsignedDigit& rhs) const;
  50.     bool operator<=(const UnsignedDigit& rhs) const;
  51.     bool operator==(const UnsignedDigit& rhs) const;
  52.  
  53.     UnsignedDigit operator+(const UnsignedDigit& rhs) const;
  54.     UnsignedDigit operator-(const UnsignedDigit& rhs) const;
  55.     UnsignedDigit operator*(const UnsignedDigit& rhs) const;
  56.     UnsignedDigit operator/(const UnsignedDigit& rhs) const;
  57.     UnsignedDigit operator%(const UnsignedDigit& rhs) const;
  58.  
  59.     UnsignedDigit operator/(int v) const;
  60.  
  61.     UnsignedDigit move(int k) const;
  62.  
  63.     string toString() const;
  64.  
  65.     friend UnsignedDigit powrt(const UnsignedDigit& x, int m);
  66.  
  67.     friend UnsignedDigit DivHelper::quasiInv(const UnsignedDigit& v);
  68.  
  69.     friend void swap(UnsignedDigit& lhs, UnsignedDigit& rhs) { swap(lhs.digits, rhs.digits); }
  70.  
  71. private:
  72.     void trim();
  73. };
  74.  
  75. class UnsignedDecimal {
  76. private:
  77.     UnsignedDigit value;
  78.     int exponent;
  79.  
  80. public:
  81.     UnsignedDecimal() : value(), exponent() {}
  82.  
  83.     UnsignedDecimal(const UnsignedDigit& value, int exponent = 0) : value(value), exponent(exponent) {}
  84.  
  85.     UnsignedDecimal(string str);
  86.  
  87.     bool operator<(const UnsignedDecimal& rhs) const;
  88.     bool operator<=(const UnsignedDecimal& rhs) const;
  89.     bool operator==(const UnsignedDecimal& rhs) const;
  90.  
  91.     UnsignedDecimal operator+(const UnsignedDecimal& rhs) const;
  92.     UnsignedDecimal operator-(const UnsignedDecimal& rhs) const;
  93.     UnsignedDecimal operator*(const UnsignedDecimal& rhs) const;
  94.  
  95.     string toString() const;
  96. };
  97.  
  98. class Int {
  99. private:
  100.     UnsignedDigit value;
  101.     int sign;
  102.  
  103.     Int(const UnsignedDigit& value, int sign) : value(value), sign(sign) {}
  104.  
  105. public:
  106.     Int() : value(), sign() {}
  107.    
  108.     Int(ll x) : value(x < 0 ? -x : x), sign(x == 0 ? 0 : x < 0 ? -1 : 1) {}
  109.  
  110.     Int(const UnsignedDigit& value) : value(value), sign(!value.zero()) {}
  111.  
  112.     Int(const string& str);
  113.  
  114.     bool operator<(const Int& rhs) const;
  115.     bool operator<=(const Int& rhs) const { return !(rhs < *this); }
  116.     bool operator>(const Int& rhs) const { return rhs < *this; }
  117.     bool operator>=(const Int& rhs) const { return !(*this < rhs); }
  118.     bool operator==(const Int& rhs) const { return sign == rhs.sign && value == rhs.value; }
  119.     bool operator!=(const Int& rhs) const { return !(*this == rhs); }
  120.    
  121.     Int operator-() const { return Int(value, -sign); }
  122.    
  123.     Int operator+(const Int& rhs) const;
  124.     Int operator-(const Int& rhs) { return *this + -rhs; }
  125.     Int operator*(const Int& rhs) { return Int(value * rhs.value, sign * rhs.sign); }
  126.     Int operator/(const Int& rhs) { return Int(value / rhs.value, sign * rhs.sign); }
  127.    
  128.     string toString() const;
  129. };
  130.  
  131. class Decimal {};
  132.  
  133. namespace ConvHelper {
  134.  
  135.     void fft(cd* a, int lgn, int d) {
  136.         int n = 1 << lgn;
  137.         {
  138.             static vector<int> brev;
  139.             if (n != brev.size()) {
  140.                 brev.resize(n);
  141.                 for (int i = 0; i < n; ++i)
  142.                     brev[i] = (brev[i >> 1] >> 1) | ((i & 1) << (lgn - 1));
  143.             }
  144.             for (int i = 0; i < n; ++i)
  145.                 if (brev[i] < i)
  146.                     swap(a[brev[i]], a[i]);
  147.         }
  148.         for (int t = 1; t < n; t <<= 1) {
  149.             cd omega(cos(PI / t), sin(PI * d / t));
  150.             for (int i = 0; i < n; i += t << 1) {
  151.                 cd* p = a + i;
  152.                 cd w(1);
  153.                 for (int j = 0; j < t; ++j) {
  154.                     cd x = p[j + t] * w;
  155.                     p[j + t] = p[j] - x;
  156.                     p[j] += x;
  157.                     w *= omega;
  158.                 }
  159.             }
  160.         }
  161.         if (d == -1) {
  162.             for (int i = 0; i < n; ++i)
  163.                 a[i] /= n;
  164.         }
  165.     }
  166.  
  167.     vector<ll> conv(const vector<int>& a, const vector<int>& b) {
  168.         int n = a.size() - 1, m = b.size() - 1;
  169.         if (n < 1000 / (m + 1) || n < 10 || m < 10) {
  170.             vector<ll> ret(n + m + 1);
  171.             for (int i = 0; i <= n; ++i)
  172.                 for (int j = 0; j <= m; ++j)
  173.                     ret[i + j] += a[i] * (ll)b[j];
  174.             return ret;
  175.         }
  176.         int lgn = 0;
  177.         while ((1 << lgn) <= n + m)
  178.             ++lgn;
  179.         vector<cd> ta(a.begin(), a.end()), tb(b.begin(), b.end());
  180.         ta.resize(1 << lgn);
  181.         tb.resize(1 << lgn);
  182.         fft(ta.begin().base(), lgn, 1);
  183.         fft(tb.begin().base(), lgn, 1);
  184.         for (int i = 0; i < (1 << lgn); ++i)
  185.             ta[i] *= tb[i];
  186.         fft(ta.begin().base(), lgn, -1);
  187.         vector<ll> ret(n + m + 1);
  188.         for (int i = 0; i <= n + m; ++i)
  189.             ret[i] = ta[i].real() + 0.5;
  190.         return ret;
  191.     }
  192.  
  193. }
  194.  
  195. namespace DivHelper {
  196.  
  197.     UnsignedDigit quasiInv(const UnsignedDigit& v) {
  198.         if (v.digits.size() == 1) {
  199.             UnsignedDigit tmp;
  200.             tmp.digits.resize(3);
  201.             tmp.digits[2] = 1;
  202.             return tmp / v.digits[0];
  203.         }
  204.         if (v.digits.size() == 2) {
  205.             UnsignedDigit sum = 0, go = 1;
  206.             vector<int> tmp(4);
  207.             go = go.move(4);
  208.             vector<UnsignedDigit> db(LGM);
  209.             db[0] = v;
  210.             for (int i = 1; i < LGM; ++i)
  211.                 db[i] = db[i - 1] + db[i - 1];
  212.             for (int i = 3; i >= 0; --i) {
  213.                 for (int k = LGM - 1; k >= 0; --k)
  214.                     if (sum + db[k].move(i) <= go) {
  215.                         sum = sum + db[k].move(i);
  216.                         tmp[i] |= 1 << k;
  217.                     }
  218.             }
  219.             return tmp;
  220.         }
  221.         int n = v.digits.size(), k = (n + 2) / 2;
  222.         UnsignedDigit tmp = quasiInv(vector<int>(v.digits.end().base() - k, v.digits.end().base()));
  223.         return (UnsignedDigit(2) * tmp).move(n - k) - (v * tmp * tmp).move(-2 * k);
  224.     }
  225.  
  226. }
  227.  
  228. UnsignedDigit::UnsignedDigit(ll x) {
  229.     while (x) {
  230.         digits.push_back(x % MOD);
  231.         x /= MOD;
  232.     }
  233.     if (digits.empty())
  234.         digits.push_back(0);
  235. }
  236.  
  237. UnsignedDigit UnsignedDigit::move(int k) const {
  238.     if (k == 0)
  239.         return *this;
  240.     if (k < 0) {
  241.         if (-k >= digits.size())
  242.             return UnsignedDigit();
  243.         return vector<int>(digits.begin().base() + (-k), digits.end().base());
  244.     }
  245.     if (digits.size() == 1 && digits[0] == 0)
  246.         return UnsignedDigit();
  247.     UnsignedDigit ret;
  248.     ret.digits.resize(k, 0);
  249.     ret.digits.insert(ret.digits.end(), digits.begin(), digits.end());
  250.     return ret;
  251. }
  252.  
  253. bool UnsignedDigit::operator<(const UnsignedDigit& rhs) const {
  254.     int n = digits.size(), m = rhs.digits.size();
  255.     if (n != m)
  256.         return n < m;
  257.     for (int i = n - 1; i >= 0; --i)
  258.         if (digits[i] != rhs.digits[i])
  259.             return digits[i] < rhs.digits[i];
  260.     return false;
  261. }
  262.  
  263. bool UnsignedDigit::operator<=(const UnsignedDigit& rhs) const {
  264.     int n = digits.size(), m = rhs.digits.size();
  265.     if (n != m)
  266.         return n < m;
  267.     for (int i = n - 1; i >= 0; --i)
  268.         if (digits[i] != rhs.digits[i])
  269.             return digits[i] < rhs.digits[i];
  270.     return true;
  271. }
  272.  
  273. bool UnsignedDigit::operator==(const UnsignedDigit& rhs) const {
  274.     int n = digits.size(), m = rhs.digits.size();
  275.     if (n != m)
  276.         return false;
  277.     return memcmp(digits.begin().base(), rhs.digits.begin().base(), n * sizeof(int)) == 0;
  278. }
  279.  
  280. UnsignedDigit UnsignedDigit::operator+(const UnsignedDigit& rhs) const {
  281.     int n = digits.size(), m = rhs.digits.size();
  282.     vector<int> tmp = digits;
  283.     if (m > n) {
  284.         tmp.resize(m + 1);
  285.         for (int i = 0; i < m; ++i)
  286.             if ((tmp[i] += rhs.digits[i]) >= MOD) {
  287.                 tmp[i] -= MOD;
  288.                 ++tmp[i + 1];
  289.             }
  290.     } else {
  291.         tmp.resize(n + 1);
  292.         for (int i = 0; i < m; ++i)
  293.             if ((tmp[i] += rhs.digits[i]) >= MOD) {
  294.                 tmp[i] -= MOD;
  295.                 ++tmp[i + 1];
  296.             }
  297.         for (int i = m; i < n; ++i)
  298.             if (tmp[i] == MOD) {
  299.                 tmp[i] = 0;
  300.                 ++tmp[i + 1];
  301.             }
  302.     }
  303.     return tmp;
  304. }
  305.  
  306. UnsignedDigit UnsignedDigit::operator*(const UnsignedDigit& rhs) const {
  307.     vector<ll> tmp = ConvHelper::conv(digits, rhs.digits);
  308.     for (int i = 0; i + 1 < tmp.size(); ++i) {
  309.         tmp[i + 1] += tmp[i] / MOD;
  310.         tmp[i] %= MOD;
  311.     }
  312.     while (tmp.back() >= MOD) {
  313.         ll remain = tmp.back() / MOD;
  314.         tmp.back() %= MOD;
  315.         tmp.push_back(remain);
  316.     }
  317.     return vector<int>(tmp.begin(), tmp.end());
  318. }
  319.  
  320. UnsignedDigit UnsignedDigit::operator/(const UnsignedDigit& rhs) const {
  321.     int m = digits.size(), n = rhs.digits.size(), t = 0;
  322.     if (m < n)
  323.         return 0;
  324.     if (m > n * 2)
  325.         t = m - 2 * n;
  326.     UnsignedDigit sv = DivHelper::quasiInv(rhs.move(t));
  327.     UnsignedDigit ret = move(t) * sv;
  328.     ret = ret.move(-2 * (n + t));
  329.     if ((ret + 1) * rhs <= *this)
  330.         ret = ret + 1;
  331.     return ret;
  332. }
  333.  
  334. UnsignedDigit UnsignedDigit::operator%(const UnsignedDigit &rhs) const {
  335.     if (digits.size() < rhs.digits.size())
  336.         return *this;
  337.     return (*this - ((*this / rhs) * rhs));
  338. }
  339.  
  340. UnsignedDigit UnsignedDigit::operator/(int k) const {
  341.     UnsignedDigit ret;
  342.     int n = digits.size();
  343.     ret.digits.resize(n);
  344.     ll r = 0;
  345.     for (int i = n - 1; i >= 0; --i) {
  346.         r = r * MOD + digits[i];
  347.         ret.digits[i] = r / k;
  348.         r %= k;
  349.     }
  350.     ret.trim();
  351.     return ret;
  352. }
  353.  
  354. UnsignedDigit UnsignedDigit::operator-(const UnsignedDigit& rhs) const {
  355.     UnsignedDigit ret(*this);
  356.     int n = rhs.digits.size();
  357.     for (int i = 0; i < n; ++i)
  358.         if ((ret.digits[i] -= rhs.digits[i]) < 0) {
  359.             ret.digits[i] += MOD;
  360.             --ret.digits[i + 1];
  361.         }
  362.     ret.trim();
  363.     return ret;
  364. }
  365.  
  366. UnsignedDigit::UnsignedDigit(const vector<int>& digits) : digits(digits) {
  367.     if (this->digits.empty())
  368.         this->digits.resize(1);
  369.     trim();
  370. }
  371.  
  372. void UnsignedDigit::trim() {
  373.     while (digits.size() > 1 && digits.back() == 0)
  374.         digits.pop_back();
  375. }
  376.  
  377. string UnsignedDigit::toString() const {
  378.     static char buf[BASE + 1];
  379.     sprintf(buf, "%d", digits.back());
  380.     string ret = buf;
  381.     int q = ret.size();
  382.     ret.resize(q + BASE * (digits.size() - 1));
  383.     int j = 0;
  384.     for (int i = (int)digits.size() - 2; i >= 0; --i) {
  385.         sprintf(const_cast<char*>(ret.c_str()) + q + j * BASE, "%05d", digits[i]);
  386.         ++j;
  387.     }
  388.     return ret;
  389. }
  390.  
  391. UnsignedDigit::UnsignedDigit(string str) {
  392.     reverse(str.begin(), str.end());
  393.     digits.resize((str.size() + BASE - 1) / BASE);
  394.     int cur = 1;
  395.     for (int i = 0; i < str.size(); ++i) {
  396.         if (i % BASE == 0)
  397.             cur = 1;
  398.         digits[i / BASE] += cur * (str[i] - '0');
  399.         cur *= 10;
  400.     }
  401.     trim();
  402. }
  403.  
  404. UnsignedDigit pow(UnsignedDigit x, int k) {
  405.     UnsignedDigit ret = 1;
  406.     while (k) {
  407.         if (k & 1)
  408.             ret = ret * x;
  409.         if (k >>= 1)
  410.             x = x * x;
  411.     }
  412.     return ret;
  413. }
  414.  
  415. DECL_IOSTREAM(UnsignedDigit)
  416. DECL_IOSTREAM(UnsignedDecimal)
  417. DECL_IOSTREAM(Int)
  418.  
  419. Int::Int(const string& str) : sign(1) {
  420.     if (str[0] == '-') {
  421.         sign = -1;
  422.         value = UnsignedDigit(string(str.begin() + 1, str.end()));
  423.     } else
  424.         value = UnsignedDigit(str);
  425.     if (value.zero())
  426.         sign = 0;
  427. }
  428.  
  429. string Int::toString() const {
  430.     if (sign < 0)
  431.         return "-" + value.toString();
  432.     return value.toString();
  433. }
  434.  
  435. Int Int::operator+(const Int& rhs) const {
  436.     if (sign == 0)
  437.         return rhs;
  438.     if (rhs.sign == 0)
  439.         return *this;
  440.     if (sign == rhs.sign)
  441.         return Int(value + rhs.value, sign);
  442.     if (value == rhs.value)
  443.         return Int();
  444.     if (rhs.value < value)
  445.         return Int(value - rhs.value, sign);
  446.     return Int(rhs.value - value, rhs.sign);
  447. }
  448.  
  449. UnsignedDigit powrt(const UnsignedDigit& x, int m) {
  450.     if (x.size() <= m) {
  451.         int l = 0, r = MOD - 1;
  452.         while (l < r) {
  453.             int mid = (l + r + 1) >> 1;
  454.             if (pow(UnsignedDigit(mid), m) <= x)
  455.                 l = mid;
  456.             else
  457.                 r = mid - 1;
  458.         }
  459.         return l;
  460.     }
  461.     if (x.size() <= m * 2) {
  462.         UnsignedDigit ret;
  463.         ret.digits.resize(2);
  464.         int l = 0, r = MOD - 1;
  465.         while (l < r) {
  466.             int mid = (l + r + 1) >> 1;
  467.             ret.digits[1] = mid;
  468.             if (pow(ret, m) <= x)
  469.                 l = mid;
  470.             else
  471.                 r = mid - 1;
  472.         }
  473.         ret.digits[1] = l;
  474.         l = 0;
  475.         r = MOD - 1;
  476.         while (l < r) {
  477.             int mid = (l + r + 1) >> 1;
  478.             ret.digits[0] = mid;
  479.             if (pow(ret, m) <= x)
  480.                 l = mid;
  481.             else
  482.                 r = mid - 1;
  483.         }
  484.         ret.digits[0] = l;
  485.         return ret;
  486.     }
  487.     int n = x.size(), take = n / m / 2;
  488.     UnsignedDigit sub((powrt(x.move(-take * m), m) + 1).move(take));
  489.     UnsignedDigit ret = (sub * (m - 1) + x / pow(sub, m - 1)) / m;
  490.     int l = max(ret.digits[0] - 10, 0), r = min(ret.digits[0] + 10, MOD - 1);
  491.     while (l < r) {
  492.             int mid = (l + r + 1) >> 1;
  493.             ret.digits[0] = mid;
  494.             if (pow(ret, m) <= x)
  495.                 l = mid;
  496.             else
  497.                 r = mid - 1;
  498.     }
  499.     ret.digits[0] = l;
  500.     return ret;
  501. }
  502.  
  503. UnsignedDecimal::UnsignedDecimal(string str) : exponent() {
  504.     int k = str.size() - 1;
  505.     while (str[k] == '0' && k)
  506.         --k;
  507.     str.erase(k + 1);
  508.     unsigned pos = str.find('.');
  509.     if (pos == str.npos) {
  510.         value = UnsignedDigit(str);
  511.         exponent = str.size() - k - 1;
  512.     } else {
  513.         exponent = -int(str.length() - pos - 1);
  514.         value = str.substr(0, pos) + str.substr(pos + 1);
  515.     }
  516. }
  517.  
  518. string UnsignedDecimal::toString() const {
  519.     string gen(value.toString());
  520.     if (exponent > 0) {
  521.         gen.insert(gen.end(), exponent, '0');
  522.     } else if (exponent < 0) {
  523.         if (-exponent >= gen.size())
  524.             gen.insert(0, -exponent - gen.size() + 1, '0');
  525.         gen.insert(gen.end() + exponent, '.');
  526.     }
  527.     return gen;
  528. }
  529.  
  530. UnsignedDecimal UnsignedDecimal::operator*(const UnsignedDecimal& rhs) const {
  531.     return UnsignedDecimal(value * rhs.value, exponent + rhs.exponent);
  532. }
  533.  
  534. UnsignedDecimal pow(UnsignedDecimal v, int k) {
  535.     UnsignedDecimal ret(1, 0);
  536.     while (k) {
  537.         if (k & 1)
  538.             ret = ret * v;
  539.         if (k >>= 1)
  540.             v = v * v;
  541.     }
  542.     return ret;
  543. }
  544.  
  545. #include <cstdio>
  546. #include <cmath>
  547. #include <ctime>
  548. #include <cstring>
  549. #include <cstdlib>
  550.  
  551. #include <algorithm>
  552. #include <numeric>
  553. #include <limits>
  554. #include <functional>
  555. #include <stack>
  556. #include <vector>
  557. #include <set>
  558. #include <map>
  559. #include <queue>
  560.  
  561. #define LOG(FMT...) fprintf(stderr, FMT)
  562.  
  563. using namespace std;
  564.  
  565. typedef long long ll;
  566. typedef unsigned long long ull;
  567.  
  568. UnsignedDecimal tst;
  569.  
  570. int main() {
  571. #ifdef LBT
  572.     freopen("test.in", "r", stdin);
  573.     int nol_cl = clock();
  574. #endif
  575.  
  576.     string str;
  577.     int k;
  578.     while (cin >> str >> k) {
  579.         tst = str;
  580.         str = pow(tst, k).toString();
  581.         if (str[0] == '0')
  582.             str.erase(0, 1);
  583.         cout << str << endl;
  584.     }
  585.  
  586. #ifdef LBT
  587.     LOG("Time: %dms\n", int((clock() - nol_cl) / (double)CLOCKS_PER_SEC * 1000));
  588. #endif
  589.     return 0;
  590. }
Advertisement
Add Comment
Please, Sign In to add comment
Public Pastes
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.  OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!