peltorator

!New Long Integers

Oct 15th, 2018
136
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.  
  20. typedef __int128 ll;
  21. typedef long double ld;
  22.  
  23. const ll T = 1e16, Q = 16, K = 10;
  24.  
  25. void printd(ll k)
  26. {
  27.     vector<int> a;
  28.     for (int i = 0; i < Q; i++)
  29.     {
  30.         a.push_back(k % K);
  31.         k /= K;
  32.     }
  33.     for (int i = Q - 1; i >= 0; i--)
  34.         cout << a[i];
  35. }
  36.  
  37. struct Integer
  38. {
  39.     int sgn;
  40.     vector<ll> dig;
  41.  
  42.     Integer()
  43.     {
  44.         sgn = 0;
  45.         dig.clear();
  46.     }
  47.  
  48.     void rem()
  49.     {
  50.         while (dig.size() && dig.back() == 0)
  51.             dig.pop_back();
  52.         if (!dig.size())
  53.         {
  54.             sgn = 0;
  55.             return;
  56.         }
  57.         for (int i = 0; i + 1 < dig.size(); i++)
  58.         {
  59.             dig[i + 1] += dig[i] / T;
  60.             dig[i] %= T;
  61.         }
  62.         while (dig.back() >= T)
  63.         {
  64.             int z = dig.size() - 1;
  65.             dig.push_back(dig[z] / T);
  66.             dig[z] %= T;
  67.  
  68.         }
  69.     }
  70.  
  71.     Integer(ll p)
  72.     {
  73.         dig.clear();
  74.         if (!p)
  75.         {
  76.             sgn = 0;
  77.             return;
  78.         }
  79.         sgn = 1;
  80.         if (p < 0)
  81.         {
  82.             sgn = -1;
  83.             p = -p;
  84.         }
  85.         ll cur = 0;
  86.         while (p)
  87.         {
  88.             ll nxt = cur * 10LL + (p % 10LL);
  89.             if (nxt >= T)
  90.             {
  91.                 dig.push_back(cur);
  92.                 cur = p % 10LL;
  93.             }
  94.             else
  95.                 cur = nxt;
  96.             p /= 10;
  97.         }
  98.         dig.push_back(cur);
  99.         (*this).rem();
  100.     }
  101.  
  102.     void print()
  103.     {
  104.         (*this).rem();
  105.         if (sgn == 0)
  106.         {
  107.             cout << "0\n";
  108.             return;
  109.         }
  110.         if (sgn == -1)
  111.             cout << "-";
  112.         cout << dig.back();
  113.         for (int i = (int)dig.size() - 2; i >= 0; i--)
  114.             printd(dig[i]);
  115.         cout << '\n';
  116.     }
  117.  
  118.     Integer operator*(const Integer &x) const
  119.     {
  120.         if (sgn == 0)
  121.             return *this;
  122.         if (x.sgn == 0)
  123.             return x;
  124.         Double ans;
  125.         ans.sgn = sgn * x.sgn;
  126.         ans.dig.assign(dig.size() + x.dig.size(), 0);
  127.         for (int i = 0; i < dig.size(); i++)
  128.             for (int j = 0; j < x.dig.size(); j++)
  129.                 ans.dig[i + j] += dig[i] * x.dig[j];
  130.         ans.rem();
  131.         return ans;
  132.     }
  133.  
  134.     bool operator==(const Integer &x) const
  135.     {
  136.         if (sgn == 0)
  137.             return x.sgn == 0;
  138.         return (sgn == x.sgn && x.dig == dig);
  139.     }
  140.  
  141.     bool operator!=(const Inteeger &x) const
  142.     {
  143.         if (sgn == 0 && x.sgn == 0)
  144.             return 0;
  145.         return (sgn != x.sgn || x.dig != dig);
  146.     }
  147.  
  148.     bool operator>(const Integer &x) const
  149.     {
  150.         if (sgn != x.sgn)
  151.             return sgn > x.sgn;
  152.         if (sgn == 0)
  153.             return 0;
  154.         if (x.dig.size() != dig.size())
  155.             return ((x.dig.size() < dig.size()) ^ (sng == -1));
  156.         for (int i = 0; i < dig.size(); i++)
  157.             if (dig[i] != x.dig[i])
  158.                 return ((sgn == -1) ^ (dig[i] > x.dig[i]));
  159.         return 0;
  160.     }
  161.  
  162.     bool operator<(const Integer &x) const
  163.     {
  164.         if (sgn != x.sgn)
  165.             return sgn < x.sgn;
  166.         if (sgn == 0)
  167.             return 0;
  168.         if (x.dig.size() != dig.size())
  169.             return ((x.dig.size() > dig.size()) ^ (sgn == -1));
  170.         for (int i = 0; i < D; i++)
  171.             if (dig[i] != x.dig[i])
  172.                 return ((sgn == -1) ^ (dig[i] < x.dig[i]));
  173.         return 0;
  174.     }
  175.  
  176.     bool operator>=(const Integer &x) const
  177.     {
  178.         return (*this) > x || (*this) == x;
  179.         if (sgn != x.sgn)
  180.             return sgn > x.sgn;
  181.         if (sgn == 0)
  182.             return 1;
  183.         if (x.dig.size() != dig.size())
  184.             return ((x.dig.size() < dig.size()) ^ (sgn == -1));
  185.         for (int i = 0; i < D; i++)
  186.             if (dig[i] != x.dig[i])
  187.                 return ((sgn == -1) ^ (dig[i] > x.dig[i]));
  188.         return 1;
  189.     }
  190.  
  191.     bool operator<=(const Integer &x) const
  192.     {
  193.         return (*this) < x || (*this) == x;
  194.         if (sgn != x.sgn)
  195.             return sgn < x.sgn;
  196.         if (sgn == 0)
  197.             return 1;
  198.         if (x.dig.size() != dig.size())
  199.             return ((x.dig.size() > dig.size()) ^ (sgn == -1));
  200.         for (int i = 0; i < D; i++)
  201.             if (dig[i] != x.dig[i])
  202.                 return ((sgn == -1) ^ (dig[i] < x.dig[i]));
  203.         return 1;
  204.     }
  205.  
  206.  
  207.     Integer operator-() const
  208.     {
  209.         Integer ans = *this;
  210.         ans.sgn = -ans.sgn;
  211.         return ans;
  212.     }
  213.  
  214.    
  215.     Integer operator-(Integer x)
  216.     {
  217.         if (x.sgn == 0)
  218.             return (*this);
  219.         if (sgn == 0)
  220.             return -x;
  221.         if (sgn != x.sgn)
  222.             return (*this) + (-x);
  223.         if (sgn == -1)
  224.             return (-x) - (-(*this));
  225.         if (x == (*this))
  226.         {
  227.             Integer y = x;
  228.             y.sgn = 0;
  229.             y.dig.clear();
  230.             return y;
  231.         }
  232.         Integer a = (*this), b = x;
  233.         bool cmp = (a > b);
  234.         if (!cmp)
  235.             swap(a, b);
  236.         Integer ans;
  237.         while (a.dig.size() < b.dig.size())
  238.             a.dig.push_back(0);
  239.         while (a.dig.size() > b.dig.size())
  240.             b.dig.push_back(0);
  241.         ans.dig.assign(a.dig.size(), 0);
  242.         for (int i = 0; i < a.dig.size(); i++)
  243.             ans.dig[i] = a.dig[i] - b.dig[i];
  244.         for (int i = (int)a.dig.size() - 1; i > 0; i--)
  245.             while (ans.dig[i] < 0)
  246.             {
  247.                 ans.dig[i] += T;
  248.                 ans.dig[i - 1]--;
  249.             }
  250.         ans.sgn = (cmp ? 1 : -1);
  251.         ans.rem();
  252.         return ans;
  253.     }
  254.  
  255.  
  256.     Integer operator+(Integer x)
  257.     {
  258.         if (sgn == 0)
  259.             return x;
  260.         if (x.sgn == 0)
  261.             return *this;
  262.         if (sgn != x.sgn)
  263.         {
  264.             return (*this) - (-x);
  265.         }
  266.         vector<ll> dig1 = dig;
  267.         while (dig1.size() < x.dig.size())
  268.             dig1.push_back(0);
  269.         while (dig1.size() > x.dig.size())
  270.             x.dig.push_back(0);
  271.         Integer ans;
  272.         ans.sgn = x.sgn;
  273.         ans.dig.assign(dig1.size(), 0);
  274.         for (int i = 0; i < dig1.size(); i++)
  275.             ans.dig[i + 1] = dig1[i] + x.dig[i];
  276.         ans.rem();
  277.         return ans;
  278.     }
  279.  
  280.     Double operator*(const int &x) const
  281.     {
  282.         return (*this) * Double(x);
  283.     }
  284. };
RAW Paste Data