Advertisement
Jasir

Bigint

Dec 1st, 2017
117
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 9.48 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. /*
  4.   ######################################################################
  5.   #######################   THE   BIG   INT   ##########################
  6. */
  7. const int base = 1000000000;
  8. const int base_digits = 9;
  9. struct bigint {
  10.     vector<int> a;
  11.     int sign;
  12.     /*<arpa>*/
  13.     int size(){
  14.     if(a.empty())return 0;
  15.     int ans=(a.size()-1)*base_digits;
  16.     int ca=a.back();
  17.     while(ca)
  18.         ans++,ca/=10;
  19.     return ans;
  20.     }
  21.     bigint operator ^(const bigint &v){
  22.     bigint ans=1,a=*this,b=v;
  23.     while(!b.isZero()){
  24.         if(b%2)
  25.         ans*=a;
  26.         a*=a,b/=2;
  27.     }
  28.     return ans;
  29.     }
  30.     string to_string(){
  31.     stringstream ss;
  32.     ss << *this;
  33.     string s;
  34.     ss >> s;
  35.     return s;
  36.     }
  37.     int sumof(){
  38.     string s = to_string();
  39.     int ans = 0;
  40.     for(auto c : s)  ans += c - '0';
  41.     return ans;
  42.     }
  43.     /*</arpa>*/
  44.     bigint() :
  45.     sign(1) {
  46.     }
  47.  
  48.     bigint(long long v) {
  49.     *this = v;
  50.     }
  51.  
  52.     bigint(const string &s) {
  53.     read(s);
  54.     }
  55.  
  56.     void operator=(const bigint &v) {
  57.     sign = v.sign;
  58.     a = v.a;
  59.     }
  60.  
  61.     void operator=(long long v) {
  62.     sign = 1;
  63.     a.clear();
  64.     if (v < 0)
  65.         sign = -1, v = -v;
  66.     for (; v > 0; v = v / base)
  67.         a.push_back(v % base);
  68.     }
  69.  
  70.     bigint operator+(const bigint &v) const {
  71.     if (sign == v.sign) {
  72.         bigint res = v;
  73.  
  74.         for (int i = 0, carry = 0; i < (int) max(a.size(), v.a.size()) || carry; ++i) {
  75.         if (i == (int) res.a.size())
  76.             res.a.push_back(0);
  77.         res.a[i] += carry + (i < (int) a.size() ? a[i] : 0);
  78.         carry = res.a[i] >= base;
  79.         if (carry)
  80.             res.a[i] -= base;
  81.         }
  82.         return res;
  83.     }
  84.     return *this - (-v);
  85.     }
  86.  
  87.     bigint operator-(const bigint &v) const {
  88.     if (sign == v.sign) {
  89.         if (abs() >= v.abs()) {
  90.         bigint res = *this;
  91.         for (int i = 0, carry = 0; i < (int) v.a.size() || carry; ++i) {
  92.             res.a[i] -= carry + (i < (int) v.a.size() ? v.a[i] : 0);
  93.             carry = res.a[i] < 0;
  94.             if (carry)
  95.             res.a[i] += base;
  96.         }
  97.         res.trim();
  98.         return res;
  99.         }
  100.         return -(v - *this);
  101.     }
  102.     return *this + (-v);
  103.     }
  104.  
  105.     void operator*=(int v) {
  106.     if (v < 0)
  107.         sign = -sign, v = -v;
  108.     for (int i = 0, carry = 0; i < (int) a.size() || carry; ++i) {
  109.         if (i == (int) a.size())
  110.         a.push_back(0);
  111.         long long cur = a[i] * (long long) v + carry;
  112.         carry = (int) (cur / base);
  113.         a[i] = (int) (cur % base);
  114.         //asm("divl %%ecx" : "=a"(carry), "=d"(a[i]) : "A"(cur), "c"(base));
  115.     }
  116.     trim();
  117.     }
  118.  
  119.     bigint operator*(int v) const {
  120.     bigint res = *this;
  121.     res *= v;
  122.     return res;
  123.     }
  124.  
  125.     void operator*=(long long v) {
  126.     if (v < 0)
  127.         sign = -sign, v = -v;
  128.     for (int i = 0, carry = 0; i < (int) a.size() || carry; ++i) {
  129.         if (i == (int) a.size())
  130.         a.push_back(0);
  131.         long long cur = a[i] * (long long) v + carry;
  132.         carry = (int) (cur / base);
  133.         a[i] = (int) (cur % base);
  134.         //asm("divl %%ecx" : "=a"(carry), "=d"(a[i]) : "A"(cur), "c"(base));
  135.     }
  136.     trim();
  137.     }
  138.  
  139.     bigint operator*(long long v) const {
  140.     bigint res = *this;
  141.     res *= v;
  142.     return res;
  143.     }
  144.  
  145.     friend pair<bigint, bigint> divmod(const bigint &a1, const bigint &b1) {
  146.     int norm = base / (b1.a.back() + 1);
  147.     bigint a = a1.abs() * norm;
  148.     bigint b = b1.abs() * norm;
  149.     bigint q, r;
  150.     q.a.resize(a.a.size());
  151.  
  152.     for (int i = a.a.size() - 1; i >= 0; i--) {
  153.         r *= base;
  154.         r += a.a[i];
  155.         int s1 = r.a.size() <= b.a.size() ? 0 : r.a[b.a.size()];
  156.         int s2 = r.a.size() <= b.a.size() - 1 ? 0 : r.a[b.a.size() - 1];
  157.         int d = ((long long) base * s1 + s2) / b.a.back();
  158.         r -= b * d;
  159.         while (r < 0)
  160.         r += b, --d;
  161.         q.a[i] = d;
  162.     }
  163.  
  164.     q.sign = a1.sign * b1.sign;
  165.     r.sign = a1.sign;
  166.     q.trim();
  167.     r.trim();
  168.     return make_pair(q, r / norm);
  169.     }
  170.  
  171.     bigint operator/(const bigint &v) const {
  172.     return divmod(*this, v).first;
  173.     }
  174.  
  175.     bigint operator%(const bigint &v) const {
  176.     return divmod(*this, v).second;
  177.     }
  178.  
  179.     void operator/=(int v) {
  180.     if (v < 0)
  181.         sign = -sign, v = -v;
  182.     for (int i = (int) a.size() - 1, rem = 0; i >= 0; --i) {
  183.         long long cur = a[i] + rem * (long long) base;
  184.         a[i] = (int) (cur / v);
  185.         rem = (int) (cur % v);
  186.     }
  187.     trim();
  188.     }
  189.  
  190.     bigint operator/(int v) const {
  191.     bigint res = *this;
  192.     res /= v;
  193.     return res;
  194.     }
  195.  
  196.     int operator%(int v) const {
  197.     if (v < 0)
  198.         v = -v;
  199.     int m = 0;
  200.     for (int i = a.size() - 1; i >= 0; --i)
  201.         m = (a[i] + m * (long long) base) % v;
  202.     return m * sign;
  203.     }
  204.  
  205.     void operator+=(const bigint &v) {
  206.     *this = *this + v;
  207.     }
  208.     void operator-=(const bigint &v) {
  209.     *this = *this - v;
  210.     }
  211.     void operator*=(const bigint &v) {
  212.     *this = *this * v;
  213.     }
  214.     void operator/=(const bigint &v) {
  215.     *this = *this / v;
  216.     }
  217.  
  218.     bool operator<(const bigint &v) const {
  219.     if (sign != v.sign)
  220.         return sign < v.sign;
  221.     if (a.size() != v.a.size())
  222.         return a.size() * sign < v.a.size() * v.sign;
  223.     for (int i = a.size() - 1; i >= 0; i--)
  224.         if (a[i] != v.a[i])
  225.         return a[i] * sign < v.a[i] * sign;
  226.     return false;
  227.     }
  228.  
  229.     bool operator>(const bigint &v) const {
  230.     return v < *this;
  231.     }
  232.     bool operator<=(const bigint &v) const {
  233.     return !(v < *this);
  234.     }
  235.     bool operator>=(const bigint &v) const {
  236.     return !(*this < v);
  237.     }
  238.     bool operator==(const bigint &v) const {
  239.     return !(*this < v) && !(v < *this);
  240.     }
  241.     bool operator!=(const bigint &v) const {
  242.     return *this < v || v < *this;
  243.     }
  244.  
  245.     void trim() {
  246.     while (!a.empty() && !a.back())
  247.         a.pop_back();
  248.     if (a.empty())
  249.         sign = 1;
  250.     }
  251.  
  252.     bool isZero() const {
  253.     return a.empty() || (a.size() == 1 && !a[0]);
  254.     }
  255.  
  256.     bigint operator-() const {
  257.     bigint res = *this;
  258.     res.sign = -sign;
  259.     return res;
  260.     }
  261.  
  262.     bigint abs() const {
  263.     bigint res = *this;
  264.     res.sign *= res.sign;
  265.     return res;
  266.     }
  267.  
  268.     long long longValue() const {
  269.     long long res = 0;
  270.     for (int i = a.size() - 1; i >= 0; i--)
  271.         res = res * base + a[i];
  272.     return res * sign;
  273.     }
  274.  
  275.     friend bigint gcd(const bigint &a, const bigint &b) {
  276.     return b.isZero() ? a : gcd(b, a % b);
  277.     }
  278.     friend bigint lcm(const bigint &a, const bigint &b) {
  279.     return a / gcd(a, b) * b;
  280.     }
  281.  
  282.     void read(const string &s) {
  283.     sign = 1;
  284.     a.clear();
  285.     int pos = 0;
  286.     while (pos < (int) s.size() && (s[pos] == '-' || s[pos] == '+')) {
  287.         if (s[pos] == '-')
  288.         sign = -sign;
  289.         ++pos;
  290.     }
  291.     for (int i = s.size() - 1; i >= pos; i -= base_digits) {
  292.         int x = 0;
  293.         for (int j = max(pos, i - base_digits + 1); j <= i; j++)
  294.         x = x * 10 + s[j] - '0';
  295.         a.push_back(x);
  296.     }
  297.     trim();
  298.     }
  299.  
  300.     friend istream& operator>>(istream &stream, bigint &v) {
  301.     string s;
  302.     stream >> s;
  303.     v.read(s);
  304.     return stream;
  305.     }
  306.  
  307.     friend ostream& operator<<(ostream &stream, const bigint &v) {
  308.     if (v.sign == -1)
  309.         stream << '-';
  310.     stream << (v.a.empty() ? 0 : v.a.back());
  311.     for (int i = (int) v.a.size() - 2; i >= 0; --i)
  312.         stream << setw(base_digits) << setfill('0') << v.a[i];
  313.     return stream;
  314.     }
  315.  
  316.     static vector<int> convert_base(const vector<int> &a, int old_digits, int new_digits) {
  317.     vector<long long> p(max(old_digits, new_digits) + 1);
  318.     p[0] = 1;
  319.     for (int i = 1; i < (int) p.size(); i++)
  320.         p[i] = p[i - 1] * 10;
  321.     vector<int> res;
  322.     long long cur = 0;
  323.     int cur_digits = 0;
  324.     for (int i = 0; i < (int) a.size(); i++) {
  325.         cur += a[i] * p[cur_digits];
  326.         cur_digits += old_digits;
  327.         while (cur_digits >= new_digits) {
  328.         res.push_back(int(cur % p[new_digits]));
  329.         cur /= p[new_digits];
  330.         cur_digits -= new_digits;
  331.         }
  332.     }
  333.     res.push_back((int) cur);
  334.     while (!res.empty() && !res.back())
  335.         res.pop_back();
  336.     return res;
  337.     }
  338.  
  339.     typedef vector<long long> vll;
  340.  
  341.     static vll karatsubaMultiply(const vll &a, const vll &b) {
  342.     int n = a.size();
  343.     vll res(n + n);
  344.     if (n <= 32) {
  345.         for (int i = 0; i < n; i++)
  346.         for (int j = 0; j < n; j++)
  347.             res[i + j] += a[i] * b[j];
  348.         return res;
  349.     }
  350.  
  351.     int k = n >> 1;
  352.     vll a1(a.begin(), a.begin() + k);
  353.     vll a2(a.begin() + k, a.end());
  354.     vll b1(b.begin(), b.begin() + k);
  355.     vll b2(b.begin() + k, b.end());
  356.  
  357.     vll a1b1 = karatsubaMultiply(a1, b1);
  358.     vll a2b2 = karatsubaMultiply(a2, b2);
  359.  
  360.     for (int i = 0; i < k; i++)
  361.         a2[i] += a1[i];
  362.     for (int i = 0; i < k; i++)
  363.         b2[i] += b1[i];
  364.  
  365.     vll r = karatsubaMultiply(a2, b2);
  366.     for (int i = 0; i < (int) a1b1.size(); i++)
  367.         r[i] -= a1b1[i];
  368.     for (int i = 0; i < (int) a2b2.size(); i++)
  369.         r[i] -= a2b2[i];
  370.  
  371.     for (int i = 0; i < (int) r.size(); i++)
  372.         res[i + k] += r[i];
  373.     for (int i = 0; i < (int) a1b1.size(); i++)
  374.         res[i] += a1b1[i];
  375.     for (int i = 0; i < (int) a2b2.size(); i++)
  376.         res[i + n] += a2b2[i];
  377.     return res;
  378.     }
  379.  
  380.     bigint operator*(const bigint &v) const {
  381.     vector<int> a6 = convert_base(this->a, base_digits, 6);
  382.     vector<int> b6 = convert_base(v.a, base_digits, 6);
  383.     vll a(a6.begin(), a6.end());
  384.     vll b(b6.begin(), b6.end());
  385.     while (a.size() < b.size())
  386.         a.push_back(0);
  387.     while (b.size() < a.size())
  388.         b.push_back(0);
  389.     while (a.size() & (a.size() - 1))
  390.         a.push_back(0), b.push_back(0);
  391.     vll c = karatsubaMultiply(a, b);
  392.     bigint res;
  393.     res.sign = sign * v.sign;
  394.     for (int i = 0, carry = 0; i < (int) c.size(); i++) {
  395.         long long cur = c[i] + carry;
  396.         res.a.push_back((int) (cur % 1000000));
  397.         carry = (int) (cur / 1000000);
  398.     }
  399.     res.a = convert_base(res.a, 6, base_digits);
  400.     res.trim();
  401.     return res;
  402.     }
  403. };
  404. /*
  405.   #######################   THE   BIG   INT   ##########################
  406.   ######################################################################
  407. */
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement