peltorator

!New Long Integers

Oct 7th, 2018
195
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <vector>
  3. #include <cstdio>
  4. #include <map>
  5. #include <algorithm>
  6. #include <cmath>
  7. #include <string>
  8. #include <cstring>
  9. #include <set>
  10. #include <queue>
  11. #include <unordered_set>
  12. #include <complex>
  13. #include <unordered_map>
  14. #include <bitset>
  15. #include <ctime>
  16. #include <cassert>
  17. #include <random>
  18.  
  19. #define sz(a) (int)((a).size())
  20.  
  21. using namespace std;
  22.  
  23. mt19937 rnd(239);
  24.  
  25. typedef __int128 ll;
  26. typedef long double ld;
  27.  
  28. const ll B = 1e16, Q = 16, T = 10;//B - BASE; T^Q = B
  29.  
  30. void printd(ll k)
  31. {
  32.     vector<int> a;
  33.     for (int i = 0; i < Q; i++)
  34.     {
  35.         a.push_back(k % T);
  36.         k /= T;
  37.     }
  38.     for (int i = Q - 1; i >= 0; i--)
  39.         cout << a[i];
  40. }
  41.  
  42. //+=, -=, *= ... need to be upgraded because now they just use operation
  43. // |, |= - not implemented fft multiplication
  44. // operations with short numbers are now implemented using transforming short numbers into big
  45. // Sqrt and dividing(/) and mod(%) by BigInt is implimented with binary search. I don't think that it's the best option
  46.  
  47. struct BigInt
  48. {
  49.     int sgn;
  50.     vector<ll> dig;
  51.  
  52.     void rem()
  53.     {
  54.         while (dig.size() && dig.back() == 0)
  55.             dig.pop_back();
  56.         if (!dig.size())
  57.             sgn = 0;
  58.     }
  59.  
  60.  
  61.     BigInt(ll x = 0)
  62.     {
  63.         if (!x)
  64.             sgn = 0;
  65.         else if (x < 0)
  66.         {
  67.             x = -x;
  68.             sgn = -1;
  69.         }
  70.         else
  71.             sgn = 1;
  72.         while (x)
  73.         {
  74.             dig.push_back(x % B);
  75.             x /= B;
  76.         }
  77.     }
  78.  
  79.     int size()
  80.     {
  81.         return dig.size();
  82.     }
  83.    
  84.     int back()
  85.     {
  86.         if (!dig.size())
  87.             return 0;
  88.         return dig.back();
  89.     }
  90.  
  91.     void rev()
  92.     {
  93.         reverse(dig.begin(), dig.end());
  94.     }
  95.  
  96.     void push_back(ll x)
  97.     {
  98.         dig.push_back(x);
  99.     }
  100.  
  101.     void read()
  102.     {
  103.         dig.clear();
  104.         string s;
  105.         cin >> s;
  106.         bool ok = 0;
  107.         for (int i = 0; i < size(); i++)
  108.             if (s[i] != '0' && s[i] != '-')
  109.             {
  110.                 ok = 1;
  111.                 break;
  112.             }
  113.         if (!ok)
  114.         {
  115.             sgn = 0;
  116.             return;
  117.         }
  118.         int l;
  119.         if (s[0] == '-')
  120.         {
  121.             sgn = -1;
  122.             l = 1;
  123.         }
  124.         else
  125.         {
  126.             sgn = 1;
  127.             l = 0;
  128.         }
  129.         for (int i = (int)s.size() - 1; i >= l; i -= Q)
  130.         {
  131.             ll cur = 0;
  132.             for (int j = max(l, i - (int)Q + 1); j <= i; j++)
  133.                 cur = T * cur + (ll)(s[j] - '0');
  134.             dig.push_back(cur);
  135.         }
  136.         (*this).rem();
  137.     }
  138.  
  139.     void print()
  140.     {
  141.         (*this).rem();
  142.         if (sgn == 0)
  143.         {
  144.             cout << "0\n";
  145.             return;
  146.         }
  147.         if (sgn == -1)
  148.             cout << '-';
  149.         cout << (long long)dig.back();
  150.         for (int i = (int)dig.size() - 2; i >= 0; i--)
  151.             printd(dig[i]);
  152.         cout << '\n';
  153.     }
  154.  
  155.     ll operator[](const int k) const
  156.     {
  157.         if (k < 0)
  158.         {
  159.             cerr << "BigInt: taking digit with negative index" << endl;
  160.             exit(0);
  161.         }
  162.         if (k >= dig.size())
  163.             return 0;
  164.         return dig[k];
  165.     }
  166.  
  167.     bool operator<(BigInt x)
  168.     {
  169.         (*this).rem();
  170.         x.rem();
  171.         if (sgn != x.sgn)
  172.             return sgn < x.sgn;
  173.         if (x.size() != dig.size())
  174.             return dig.size() < x.size();
  175.         for (int i = x.size() - 1; i >= 0; i--)
  176.             if (x[i] != dig[i])
  177.                 return dig[i] < x[i];
  178.         return 0;
  179.     }
  180.  
  181.     bool operator>(BigInt x)
  182.     {
  183.         (*this).rem();
  184.         x.rem();
  185.         if (sgn != x.sgn)
  186.             return sgn > x.sgn;
  187.         if (x.size() != dig.size())
  188.             return dig.size() > x.size();
  189.         for (int i = x.size() - 1; i >= 0; i--)
  190.             if (x[i] != dig[i])
  191.                 return dig[i] > x[i];
  192.         return 0;
  193.     }
  194.  
  195.     bool operator<=(BigInt x)
  196.     {
  197.         (*this).rem();
  198.         x.rem();
  199.         if (sgn != x.sgn)
  200.             return sgn < x.sgn;
  201.         if (x.size() != dig.size())
  202.             return dig.size() < x.size();
  203.         for (int i = x.size() - 1; i >= 0; i--)
  204.             if (x[i] != dig[i])
  205.                 return dig[i] < x[i];
  206.         return 1;
  207.     }
  208.  
  209.     bool operator>=(BigInt x)
  210.     {
  211.         (*this).rem();
  212.         x.rem();
  213.         if (sgn != x.sgn)
  214.             return sgn > x.sgn;
  215.         if (x.size() != dig.size())
  216.             return dig.size() > x.size();
  217.         for (int i = x.size() - 1; i >= 0; i--)
  218.             if (x[i] != dig[i])
  219.                 return dig[i] > x[i];
  220.         return 1;
  221.     }
  222.  
  223.     bool operator==(BigInt x)
  224.     {
  225.         (*this).rem();
  226.         x.rem();
  227.         return sgn == x.sgn && dig == x.dig;  
  228.     }
  229.  
  230.     bool operator!=(BigInt x)
  231.     {
  232.         (*this).rem();
  233.         x.rem();
  234.         return sgn != x.sgn || dig != x.dig;
  235.     }
  236.  
  237.     BigInt operator-() const
  238.     {
  239.         BigInt ret = (*this);
  240.         ret.sgn = -sgn;
  241.         return ret;
  242.     }
  243.  
  244.     void assign(int k, ll zn = 0)
  245.     {
  246.         dig.assign(k, zn);
  247.     }
  248.  
  249.     void resize(int k)
  250.     {
  251.         while (dig.size() < k)
  252.             dig.push_back(0);
  253.     }
  254.  
  255.     BigInt operator-(BigInt x)
  256.     {
  257.         x.rem();
  258.         (*this).rem();
  259.         if (x.sgn == 0)
  260.             return (*this);
  261.         if (sgn == 0)
  262.             return (-x);
  263.         if (sgn != x.sgn)
  264.         {
  265.             if (sgn == 1)
  266.                 return ((*this) + (-x));
  267.             else
  268.                 return (x + (-(*this)));
  269.         }
  270.         bool rev = 0;
  271.         if (sgn == -1)
  272.         {
  273.             sgn = 1;
  274.             x.sgn = 1;
  275.             rev = 1;
  276.         }
  277.         if ((*this) < x)
  278.         {
  279.             if (rev)
  280.             {
  281.                 sgn = -1;
  282.                 x.sgn = -1;
  283.             }
  284.             return -(x - (*this));
  285.         }
  286.         BigInt ans;
  287.         ans.assign(max(x.size(), (int)dig.size()));
  288.         for (int i = 0; i < ans.size(); i++)
  289.             ans.dig[i] = dig[i] - x[i];
  290.         for (int i = 0; i < ans.size(); i++)
  291.         {
  292.             if (ans[i] < 0)
  293.             {
  294.                 ans.dig[i] += B;
  295.                 ans.dig[i + 1]--;
  296.             }
  297.         }
  298.         if (rev)
  299.         {
  300.             sgn = -1;
  301.             x.sgn = -1;
  302.         }
  303.         ans.sgn = sgn;
  304.         ans.rem();
  305.         return ans;
  306.     }
  307.  
  308.     BigInt operator+(BigInt x)
  309.     {
  310.         x.rem();
  311.         (*this).rem();
  312.         if (x.sgn == 0)
  313.             return (*this);
  314.         if (sgn == 0)
  315.             return x;
  316.         if (sgn != x.sgn)
  317.         {
  318.             if (sgn == 1)
  319.                 return ((*this) - (-x));
  320.             else
  321.                 return (x - (-(*this)));
  322.         }
  323.         BigInt ans;
  324.         ans.assign(max(x.size(), (int)dig.size()) + 1);
  325.         for (int i = 0; i < ans.size(); i++)
  326.             ans.dig[i] = x[i] + dig[i];
  327.         for (int i = 0; i + 1 < ans.size(); i++)
  328.         {
  329.             if (ans[i] >= B)
  330.             {
  331.                 ans.dig[i] -= B;
  332.                 ans.dig[i + 1]++;
  333.             }
  334.         }
  335.         ans.sgn = sgn;
  336.         ans.rem();
  337.         return ans;
  338.     }
  339.  
  340.     void operator+=(BigInt x)
  341.     {
  342.         (*this) = (*this) + x;
  343.     }
  344.    
  345.     void operator-=(BigInt x)
  346.     {
  347.         (*this) = (*this) - x;
  348.     }
  349.  
  350.     BigInt operator+(ll x)// TODO NEED TO BE UPGRADED
  351.     {
  352.         return (*this) + BigInt(x);    
  353.     }
  354.  
  355.     BigInt operator-(ll x)
  356.     {
  357.         return (*this) - BigInt(x);
  358.     }
  359.  
  360.     void operator+=(ll x)
  361.     {
  362.         (*this) = (*this) + BigInt(x);
  363.     }
  364.  
  365.     void operator-=(ll x)
  366.     {
  367.         (*this) = (*this) - BigInt(x);
  368.     }
  369.    
  370.     BigInt operator*(BigInt x)
  371.     {
  372.         x.rem();
  373.         (*this).rem();
  374.         BigInt ans;
  375.         ans.assign(x.size() + dig.size() + 1);
  376.         for (int i = 0; i < x.size(); i++)
  377.             for (int j = 0; j < dig.size(); j++)
  378.                 ans.dig[i + j] += x[i] * dig[j];
  379.         ans.sgn = x.sgn * sgn;
  380.         ans.rem();
  381.         return ans;
  382.     }
  383.  
  384.     void operator*=(BigInt x)
  385.     {
  386.         (*this) = (*this) * x;
  387.     }
  388.  
  389.     BigInt operator*(ll x)
  390.     {
  391.         return (*this) * BigInt(x);
  392.     }
  393.  
  394.     void operator*=(ll x)
  395.     {
  396.         (*this) = (*this) * BigInt(x);
  397.     }
  398.  
  399.     BigInt operator|(BigInt x)
  400.     {
  401.         //TODO (FFT multiplication)
  402.         cerr << "BigInt: fft multiplication with | isn't implemented yet" << endl;
  403.         exit(0);
  404.         return x;
  405.     }
  406.  
  407.     void operator|=(BigInt x)
  408.     {
  409.         cerr << "BigInt: fft multiplication with |= isn't implemented yet" << endl;
  410.         exit(0);
  411.  
  412.         //TODO (FFT multiplication)
  413.     }
  414.  
  415.     BigInt operator/(ll x)
  416.     {
  417.         if (x == 0)
  418.         {
  419.             cerr << "BigInt: dividing by short zero" << endl;
  420.             exit(0);
  421.         }
  422.         ll carry = 0;
  423.         BigInt ans;
  424.         ans.assign(dig.size());
  425.         for (int i = (int)dig.size() - 1; i >= 0; i--)
  426.         {
  427.             carry = carry * B + dig[i];
  428.             ans.dig[i] = carry / x;
  429.             carry %= x;
  430.         }
  431.         ans.rem();
  432.         return ans;
  433.     }
  434.  
  435.     void operator/=(ll x)
  436.     {
  437.         (*this) = (*this) / x;
  438.     }
  439.  
  440.     BigInt operator/(BigInt x)
  441.     {
  442.         x.rem();
  443.         (*this).rem();
  444.         if (x.sgn == 0)
  445.         {
  446.             cerr << "BigInt: dividing by big zero" << endl;
  447.             exit(0);
  448.         }
  449.         if (sgn == 0)
  450.             return (*this);
  451.         int newsgn = sgn * x.sgn;
  452.         BigInt a = (*this);
  453.         a.sgn = 1;
  454.         BigInt b = x;
  455.         b.sgn = 1;
  456.         BigInt l(0), r = a + 1;
  457.         while (l + 1 != r)
  458.         {
  459.             BigInt mid = (r + l) / 2;
  460.             if (mid * b > a)
  461.                 r = mid;
  462.             else
  463.                 l = mid;
  464.         }
  465.         return l;
  466.     }
  467.  
  468.     void operator/=(BigInt x)
  469.     {
  470.         (*this) = (*this) / x;
  471.     }
  472.  
  473.     BigInt operator%(BigInt x)
  474.     {
  475.         return (*this) - ((*this) / x) * x;
  476.     }
  477.  
  478.     void operator %=(BigInt x)
  479.     {
  480.         (*this) = (*this) % x;
  481.     }
  482.  
  483.     BigInt operator^(ll k) // power
  484.     {
  485.         if (k < 0)
  486.             return BigInt(0);
  487.         if (!k)
  488.             return BigInt(1);
  489.         BigInt ans = (*this);
  490.         vector<int> a;
  491.         while (k)
  492.         {
  493.             a.push_back(k % 2);
  494.             k /= 2;
  495.         }
  496.         a.pop_back();
  497.         reverse(a.begin(), a.end());
  498.         for (int i : a)
  499.         {
  500.             ans *= ans;
  501.             if (i)
  502.                 ans *= (*this);
  503.         }
  504.         return ans;
  505.     }
  506.  
  507.     void operator^=(ll k)
  508.     {
  509.         (*this) = ((*this) ^ k);
  510.     }
  511. };
  512.  
  513. BigInt factorial(int x)
  514. {
  515.     BigInt ans(1);
  516.     for (int i = 2; i <= x; i++)
  517.         ans *= (ll)i;
  518.     return ans;
  519. }
  520.  
  521. BigInt Sqrt(BigInt x)
  522. {
  523.     x.rem();
  524.     if (x.sgn == -1)
  525.     {
  526.         cout << "BigInt trying to take sqrt of negative number" << endl;
  527.         exit(0);
  528.     }
  529.     if (x.sgn == 0)
  530.         return x;
  531.     BigInt l = 0, r = x + 1;
  532.     while (l + 1 != r)
  533.     {
  534.         BigInt mid = (r + l) / 2;
  535.         if (mid * mid > x)
  536.             r = mid;
  537.         else
  538.             l = mid;
  539.     }
  540.     return l;
  541. }
RAW Paste Data