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

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!