API tools faq
paste
Advertisement
BaoJIaoPisu

Untitled

BaoJIaoPisu
Jan 18th, 2022
81
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 11.32 KB | None | 0 0
raw download clone embed print report
  1. const int Dig = 10;
  2. struct BigNum {
  3.     deque<int> num;
  4.     int sign = 1;
  5.  
  6.     //constructor
  7.     BigNum() {
  8.     }
  9.     BigNum(long long x) {
  10.         num.clear();
  11.         if (x < 0)
  12.             sign = -1, x = -x;
  13.         if (x == 0)
  14.             num.push_back(x);
  15.         while (x > 0) {
  16.             num.push_back(x % Dig);
  17.             x /= Dig;
  18.         }
  19.     }
  20.     BigNum(int x) {
  21.         num.clear();
  22.         if (x < 0)
  23.             sign = -1, x = -x;
  24.         if (x == 0)
  25.             num.push_back(x);
  26.         while (x > 0) {
  27.             num.push_back(x % Dig);
  28.             x /= Dig;
  29.         }
  30.     }
  31.     BigNum(const BigNum &x) {
  32.         sign = x.sign;
  33.         num = x.num;
  34.     }
  35.  
  36.     // change to int
  37.     friend int BtoI(const BigNum &x) {
  38.         int res = 0, t = 1;
  39.         for (int i = 0; i < x.num.size(); i++)
  40.             res += t * x.num[i];
  41.         return res;
  42.        
  43.     }
  44.  
  45.     //absolut
  46.     friend BigNum abs(const BigNum &x) {
  47.         BigNum res = x;
  48.         res.sign = 1;
  49.         return res;
  50.     }
  51.  
  52.     //clear 0
  53.     void clr() {
  54.         while (!num.empty() and !num.back())
  55.             num.pop_back();
  56.     }
  57.  
  58.     //normalize
  59.     void normalize() {
  60.         (*this).clr();
  61.         int carry = 0;
  62.         for (int i = 0; i < num.size(); i++) {
  63.             int t = num[i] + carry;
  64.             if (t < 0) {
  65.                 t += Dig;
  66.                 carry = -1;
  67.                 num[i] = t;
  68.             }
  69.             else {
  70.                 num[i] = t % Dig;
  71.                 carry = t / Dig;
  72.             }
  73.         }
  74.         if (carry > 0)
  75.             num.push_back(carry);
  76.         if (carry < 0) {
  77.             sign *= -1;
  78.             num.push_back(-carry);
  79.         }
  80.         (*this).clr();
  81.         if (num.empty())
  82.             sign = 1;
  83.        
  84.     }
  85.  
  86.     //is 0
  87.     bool isZero() {
  88.         (*this).normalize();
  89.         return num.empty();
  90.     }
  91.  
  92.     //compare operators
  93.     bool operator<(const BigNum &x) const {
  94.         if (sign != x.sign)
  95.             return sign < x.sign;
  96.         bool res = false, flag = false;
  97.         if (num.size() != x.num.size()) {
  98.             res = (num.size() < x.num.size());
  99.             flag = true;
  100.         }
  101.         else {
  102.             for (int i = num.size() - 1; i >= 0; i--)
  103.                 if (num[i] != x.num[i]) {
  104.                     flag = true;
  105.                     res = (num[i] < x.num[i]);
  106.                     break;
  107.                 }
  108.         }
  109.         if (!flag)
  110.             return false;
  111.         if (sign == -1)
  112.             return !res;
  113.         return res;
  114.     }
  115.     bool operator==(const BigNum &x) const {
  116.         if (sign == x.sign and num.size() == x.num.size()) {
  117.             bool res = true;
  118.             for (int i = 0; i < num.size() and res; i++)
  119.                 if (num[i] != x.num[i])
  120.                     res = false;
  121.             return res;
  122.         }
  123.         else
  124.             return false;
  125.     }
  126.     bool operator<=(const BigNum &x) const {
  127.         return (((*this) < x) or ((*this) == x));
  128.     }
  129.     bool operator>(const BigNum &x) const {
  130.         return (!((*this) <= x));
  131.     }
  132.     bool operator>=(const BigNum &x) const {
  133.         return (!((*this) < x));
  134.     }
  135.     bool operator!=(const BigNum &x) const {
  136.         return (!((*this) == x));
  137.     }
  138.     friend BigNum max(const BigNum &x, const BigNum &y) {
  139.         return (x > y? x: y);
  140.     }
  141.     friend BigNum min(const BigNum &x, const BigNum &y) {
  142.         return (x < y? x: y);
  143.     }
  144.  
  145.     //math operators
  146.     BigNum operator+(const BigNum &x) const {
  147.         if (sign == x.sign) {
  148.             BigNum res;
  149.             res.sign = sign;
  150.             for (int i = 0; i < max(x.num.size(), num.size()); i++) {
  151.                 int t = (i >= num.size()? 0: num[i]) + (i >= x.num.size()? 0: x.num[i]);
  152.                 res.num.push_back(t);
  153.             }
  154.             res.normalize();
  155.             return res;
  156.         }
  157.         if (sign == -1)
  158.             return x - abs(*this);
  159.         else
  160.             return (*this) - abs(x);
  161.     }
  162.     BigNum operator-(const BigNum &x) const {
  163.         if (sign == x.sign) {
  164.             BigNum res, a = abs(*this), b = abs(x);
  165.             a.clr();
  166.             b.clr();
  167.             if (a == b) {
  168.                 res = 0;
  169.                 return res;
  170.             }
  171.             if (b < a) {
  172.                 for (int i = 0; i < a.num.size(); i++) {
  173.                     int t = a.num[i] - (i >= b.num.size()? 0: b.num[i]);
  174.                     res.num.push_back(t);
  175.                 }
  176.                 res.normalize();
  177.             }
  178.             else {
  179.                 for (int i = 0; i < b.num.size(); i++) {
  180.                     int t = b.num[i] - (i >= a.num.size()? 0: a.num[i]);
  181.                     res.num.push_back(t);
  182.                 }
  183.                 res.normalize();
  184.                 res.sign *= -1;
  185.             }
  186.             if (sign == -1)
  187.                 res.sign *= -1;
  188.             return res;
  189.         }
  190.         if (sign == -1) {
  191.             BigNum res = abs(*this) + x;
  192.             res.sign *= -1;
  193.             return res;
  194.         }
  195.         else
  196.             return (*this) + abs(x);
  197.     }
  198.     void operator+=(const BigNum &x) {
  199.         (*this) = (*this) + x;
  200.     }
  201.     void operator-=(const BigNum &x) {
  202.         (*this) = (*this) - x;
  203.     }
  204.     void operator++() {
  205.         (*this) += 1;
  206.     }
  207.     BigNum operator++(int) {
  208.         BigNum res;
  209.         ++(*this);
  210.         return res;
  211.     }
  212.     void operator--() {
  213.         (*this) -= 1;
  214.     }
  215.     BigNum operator--(int) {
  216.         BigNum res;
  217.         --(*this);
  218.         return res;
  219.     }
  220.     BigNum operator*(const BigNum &x) const {
  221.         BigNum res;
  222.         BigNum a = (*this), b = x;
  223.         if (a.isZero() or b.isZero())
  224.             return 0;
  225.         a.clr();
  226.         b.clr();
  227.         for (int i = 0; i < b.num.size(); i++) {
  228.             BigNum t;
  229.             for (int j = 1; j <= i; j++)
  230.                 t.num.push_back(0);
  231.             for (int j = 0; j < a.num.size(); j++)
  232.                 t.num.push_back(a.num[j] * b.num[i]);
  233.             t.normalize();
  234.             res += t;
  235.         }
  236.         res.normalize();
  237.         res.sign = a.sign * b.sign;
  238.         return res;
  239.     }
  240.     void operator*=(const BigNum &x) {
  241.         (*this) = (*this) * x;
  242.     }
  243.     friend pair<BigNum, BigNum> dmod(const BigNum &x, const BigNum &y) {
  244.         BigNum res, a = abs(x), b = abs(y), carry;
  245.         res.sign = y.sign * x.sign;
  246.         a.clr();
  247.         b.clr();
  248.         if (b.isZero())
  249.             return {-1, -1};
  250.         if (a < b) {
  251.             return {0, x};
  252.         }
  253.         int cnt = a.num.size() - 1;
  254.         for (int i = a.num.size() - 1; carry < b; i--) {
  255.             carry.num.push_front(a.num[i]);
  256.             cnt = i - 1;
  257.         }
  258.         for (int i = 1; i <= 10; i++) {
  259.             BigNum t = b * i;
  260.             if (t > carry) {
  261.                 res.num.push_front(i - 1);
  262.                 t -= b;
  263.                 carry -= t;
  264.                 break;
  265.             }
  266.         }
  267.         for (int i = cnt; i >= 0; i--) {
  268.             carry.num.push_front(a.num[i]);
  269.             carry.normalize();
  270.             if (carry >= b) {
  271.                 for (int j = 1; j <= 10; j++) {
  272.                     BigNum t = b * j;
  273.                     if (t > carry) {
  274.                         res.num.push_front(j - 1);
  275.                         t -= b;
  276.                         carry -= t;
  277.                         break;
  278.                     }
  279.                 }
  280.             }
  281.             else {
  282.                 res.num.push_front(0);
  283.             }
  284.         }
  285.         res.normalize();
  286.         if (res.sign == -1)
  287.             carry = y - x;
  288.         return {res, carry};
  289.  
  290.     }
  291.     BigNum operator/(const BigNum &x) const {
  292.         pair<BigNum, BigNum> res = dmod((*this), x);
  293.         return res.first;
  294.     }
  295.     void operator/=(const BigNum &x) {
  296.         (*this) = (*this) / x;
  297.     }
  298.     BigNum operator%(const BigNum &x) const {
  299.         pair<BigNum, BigNum> res = dmod((*this), x);
  300.         return res.second;
  301.     }
  302.     void operator%=(const BigNum &x) {
  303.         (*this) = (*this) % x;
  304.     }
  305.     friend BigNum pow(const BigNum &x, const BigNum &y) {
  306.         BigNum tmp = y;
  307.         if (tmp.isZero())
  308.             return 1;
  309.         BigNum res = 1, t = y, a = x;
  310.             pair<BigNum, BigNum> dm;
  311.         while (t > 0) {
  312.             if ((t % 2) == 1)
  313.                 res = res * a;
  314.             a *= a;
  315.             t /= 2;
  316.         }
  317.         return res;
  318.     }
  319.     friend BigNum gcd(BigNum x, BigNum y) {
  320.         return (y.isZero()? x: gcd(y, x % y));
  321.     }
  322.     friend BigNum lcm(const BigNum &x, const BigNum &y) {
  323.         return (x * y) / gcd(x, y);
  324.     }
  325.     friend BigNum sqrt(const BigNum &x) {
  326.         if (x.sign == -1)
  327.             return -1;
  328.         BigNum carry, res, lef;
  329.         deque<pair<int, int>> t;
  330.         for (int i = 0; i < x.num.size(); i += 2) {
  331.             if (i + 1 == x.num.size())
  332.                 t.push_front({x.num[i], 1});
  333.             else
  334.                 t.push_front({x.num[i] + x.num[i + 1] * 10, 2});
  335.         }
  336.         for (int i = 0; i < t.size(); i++) {
  337.             if (t[i].second == 1)
  338.                 carry.num.push_front(t[i].first);
  339.             else
  340.                 carry.num.push_front(t[i].first / 10), carry.num.push_front(t[i].first % 10);
  341.             carry.normalize();
  342.             lef.num.push_front(0);
  343.             for (int i = 1; i <= 10; i++) {
  344.                 lef.num[0] = i;
  345.                 BigNum tmp = (lef) * i;
  346.                 if (tmp > carry) {
  347.                     lef.num[0] = i - 1;
  348.                     tmp = lef * (i - 1);
  349.                     carry -= tmp;
  350.                     lef += (i - 1);
  351.                     res.num.push_front(i - 1);
  352.                     break;
  353.                 }
  354.             }
  355.         }
  356.         res.normalize();
  357.         return res;
  358.     }
  359.  
  360.     //string to BigNum and BigNum to string
  361.     void toBig(string &s) {
  362.         if (s[0] == '-') {
  363.             sign = -1;
  364.             s = s.substr(1);
  365.         }
  366.         else
  367.             sign = 1;
  368.         reverse(s.begin(), s.end());
  369.         num.clear();
  370.         for (int i = (s[0] == '-'); i < s.size(); i += Dig / 10) {
  371.             string sp;
  372.             for (int j = i; j < i + (Dig / 10); j++)
  373.                 sp += s[j];
  374.             long long t = stol(sp);
  375.             num.push_back(t);
  376.         }
  377.     }
  378.     friend string to_string(const BigNum &x) {
  379.         string res;
  380.         if (x.num.empty()) {
  381.             res += '0';
  382.             return res;
  383.         }
  384.         if (x.sign == -1)
  385.             res += '-';
  386.         for (int i = x.num.size() - 1; i >= 0; i--) {
  387.             string t = to_string(x.num[i]);
  388.             reverse(t.begin(), t.end());
  389.             res += t;
  390.         }
  391.         return res;
  392.     }
  393.     //change base
  394.     friend BigNum change_base(const BigNum &a, const int y, const int x) {
  395.         if (y == x)
  396.             return a;
  397.         BigNum res, t = change_base_rev(a, y, 10);
  398.         t.normalize();
  399.         while (t > 0) {
  400.             res.num.push_back(BtoI(t % x));
  401.             t /= x;
  402.         }
  403.         return res;
  404.     }
  405.     friend BigNum change_base_rev(const BigNum &a, const int y, const int x) {
  406.         if (y == x)
  407.             return a;
  408.         if (x == 10) {
  409.             BigNum res, t = 1, b = a;
  410.             b.clr();
  411.             for (int i = 0; i < b.num.size(); i++)
  412.                 res += t * b.num[i], t *= y;
  413.             return res;
  414.         }
  415.         BigNum t = change_base_rev(a, y, 10);
  416.         return change_base(t, 10, x);
  417.  
  418.     }
  419.     friend BigNum CB(const BigNum &a, int y, int x) {
  420.         if (x > y)
  421.             return change_base_rev(a, y, x);
  422.         return change_base(a, y, x);
  423.     }
  424.  
  425.     //bitwisse operator
  426.     BigNum operator^(const BigNum &x) const {
  427.         BigNum res, a = change_base(*this, 10, 2), b = change_base(x, 10, 2);
  428.         for (int i = 0; i < max(a.num.size(), b.num.size()); i++) {
  429.             int d1 = 0, d2 = 0;
  430.             if (i < a.num.size())
  431.                 d1 = a.num[i];
  432.             if (i < b.num.size())
  433.                 d2 = b.num[i];
  434.             res.num.push_back(d1 ^ d2);
  435.         }
  436.         res.clr();
  437.         res = change_base_rev(res, 2, 10);
  438.         res.normalize();
  439.         return res;
  440.     }
  441.     BigNum operator&(const BigNum &x) const {
  442.         BigNum res, a = change_base(*this, 10, 2), b = change_base(x, 10, 2);
  443.         for (int i = 0; i < max(a.num.size(), b.num.size()); i++) {
  444.             int d1 = 0, d2 = 0;
  445.             if (i < a.num.size())
  446.                 d1 = a.num[i];
  447.             if (i < b.num.size())
  448.                 d2 = b.num[i];
  449.             res.num.push_back(d1 & d2);
  450.         }
  451.         res.clr();
  452.         res = change_base_rev(res, 2, 10);
  453.         res.normalize();
  454.         return res;
  455.     }
  456.     BigNum operator|(const BigNum &x) const {
  457.         BigNum res, a = change_base(*this, 10, 2), b = change_base(x, 10, 2);
  458.         for (int i = 0; i < max(a.num.size(), b.num.size()); i++) {
  459.             int d1 = 0, d2 = 0;
  460.             if (i < a.num.size())
  461.                 d1 = a.num[i];
  462.             if (i < b.num.size())
  463.                 d2 = b.num[i];
  464.             res.num.push_back(d1 | d2);
  465.         }
  466.         res.clr();
  467.         res = change_base_rev(res, 2, 10);
  468.         res.normalize();
  469.         return res;
  470.     }
  471.     void operator^=(const BigNum &x) {
  472.         (*this) = (*this) ^ x;
  473.     }
  474.     void operator&=(const BigNum &x) {
  475.         (*this) = (*this) & x;
  476.     }
  477.     void operator|=(const BigNum &x) {
  478.         (*this) = (*this) | x;
  479.     }
  480.     BigNum operator<<(const BigNum &x) {
  481.         BigNum res = change_base((*this), 10, 2);
  482.         for (BigNum i = 0; i < x; i++)
  483.             res.num.push_front(0);
  484.         res = change_base_rev(res, 2, 10);
  485.         res.normalize();
  486.         return res;
  487.     }
  488.     BigNum operator>>(const BigNum &x) {
  489.         BigNum res = change_base((*this), 10, 2);
  490.         BigNum t = (int)res.num.size();
  491.         for (BigNum i = 0; i < min(x, t); i++)
  492.             res.num.pop_front();
  493.         res = change_base_rev(res, 2, 10);
  494.         res.normalize();
  495.         return res;
  496.  
  497.     }
  498.     void operator>>=(const BigNum &x) {
  499.         (*this) = (*this) >> x;
  500.     }
  501.     void operator<<=(const BigNum &x) {
  502.         (*this) = (*this) << x;
  503.     }
  504.  
  505.  
  506.     //cin and cout
  507.     friend istream& operator>>(istream &stream, BigNum &x) {
  508.         string s;
  509.         stream >> s;
  510.         x.toBig(s);
  511.         return stream;
  512.     }
  513.     friend ostream& operator<<(ostream &stream, BigNum &x) {
  514.         if (x.num.empty()) {
  515.             stream << 0;
  516.             return stream;
  517.         }
  518.         if (!x.num.empty() and x.sign == -1)
  519.             stream << '-';
  520.         stream << (x.num.empty() ? 0 : x.num.back());
  521.         for (int i = (int) x.num.size() - 2; i >= 0; i--)
  522.             stream  << x.num[i];
  523.         return stream;
  524.     }
  525.    
  526. };
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement
Public Pastes
Advertisement
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!