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