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

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!