BigInt in C++

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
namespace fft
{
    const int mod = -1;
    class cpx
    {
    public:
        double r, i;
        cpx(double _r = 0, double _i = 0) : r(_r), i(_i) {}
        cpx operator+(cpx b) { return {r + b.r, i + b.i}; }
        cpx operator-(cpx b) { return {r - b.r, i - b.i}; }
        cpx operator*(cpx b) { return {r * b.r - i * b.i, r * b.i + i * b.r}; }
        cpx operator/(double b) { return {r / b, i / b}; }
        inline cpx conj() { return {r, -i}; }
    };
    const double PI = acos(-1);
    vector<int> rev(1, 0); // rev has [base] bits
    vector<cpx> roots;
    int base = 0;
    void precompute(int nbase)
    {
        if (nbase <= base)
            return;
        rev.resize(1 << nbase);
        for (int i = 0; i < (1 << nbase); ++i)
        {
            rev[i] = rev[i >> 1] >> 1 | ((i & 1) << (nbase - 1));
        }
        roots.resize(1 << nbase);
        for (; base < nbase; ++base)
        {
            int len = 1 << base;
            double angle = 2 * PI / (1 << (base + 1));
            for (int i = 0; i < len; ++i)
            {
                double cur = angle * i;
                roots[len + i] = cpx(cos(cur), sin(cur));
            }
        }
    }
    void fft(vector<cpx> &a, int n = -1)
    {
        if (n == -1)
            n = a.size();
        assert((n & (n - 1)) == 0);
        int zeros = __builtin_ctz(n);
        precompute(zeros);
        int shift = base - zeros;
        for (int i = 0; i < n; ++i)
        {
            if (i < (rev[i] >> shift))
                swap(a[i], a[rev[i] >> shift]);
        }
        for (int len = 1; len < n; len <<= 1)
            for (int i = 0; i < n; i += 2 * len)
                for (int j = 0; j < len; ++j)
                {
                    cpx u = a[i + j], v = a[i + j + len] * roots[len + j];
                    a[i + j] = u + v;
                    a[i + j + len] = u - v;
                }
    }
    vector<cpx> fa, fb;
    vector<ll> multiply(const vector<int> &a, const vector<int> &b)
    {
        if (a.empty() || b.empty())
            return {};
        int sz = a.size() + b.size() - 1;
        int n = sz == 1 ? 1 : 1 << (32 - __builtin_clz(sz - 1));
        if (n > fa.size())
            fa.resize(n);
        for (int i = 0; i < n; ++i)
        {
            int x = i < a.size() ? a[i] : 0;
            int y = i < b.size() ? b[i] : 0;
            fa[i] = cpx(x, y);
        }
        fft(fa, n);
        cpx r(0, -0.5 / n);
        for (int i = 0; i <= (n >> 1); ++i)
        {
            int j = (n - i) & (n - 1);
            cpx x = (fa[i] + fa[j].conj()) / 2;
            cpx y = (fa[i] - fa[j].conj()) * r;
            fa[i] = x * y;
            if (i != j)
                fa[j] = fa[i].conj();
        }
        fft(fa, n);
        reverse(fa.begin() + 1, fa.begin() + n);
        vector<ll> res(sz);
        for (int i = 0; i < sz; ++i)
        {
            res[i] = llround(fa[i].r);
        }
        return res;
    }
} // namespace fft
const int BASE = 1000; // Must be power of 10, use 1000 for FFT stability (BASE^2 * |maxNumSize| <= 1e15)
const int BASE_DIGITS = log10(BASE);
class BigInt
{
private:
    bool neg = false; // false for *this == 0.
    vector<int> num;
public:
    BigInt() {}
    /* Can have leading zeros or empty (e.g. "-000123", "0123", "00", "0", ""). */
    BigInt(const string &s)
    {
        int st = 0;
        if (s[0] == '-')
        {
            neg = true;
            st = 1;
        }
        for (int i = (int)s.size() - 1; i >= st; i -= BASE_DIGITS)
        {
            int x = 0;
            for (int j = max(st, i - BASE_DIGITS + 1); j <= i; ++j)
                x = x * 10 + s[j] - '0';
            num.push_back(x);
        }
        trim();
    }
    BigInt(ll m)
    {
        if (m < 0)
            neg = true;
        while (m)
        {
            num.push_back(abs(m % BASE));
            m /= BASE;
        }
    }
    void trim()
    {
        while (!num.empty() && !num.back())
            num.pop_back();
        if (num.empty())
            neg = false;
    }
    bool operator<(const BigInt &v) const
    {
        if (neg != v.neg)
            return neg > v.neg;
        if (num.size() != v.num.size())
            return neg ? num.size() > v.num.size() : num.size() < v.num.size();
        for (int i = (int)num.size() - 1; i >= 0; --i)
            if (num[i] != v.num[i])
                return neg ? num[i] > v.num[i] : num[i] < v.num[i];
        return false;
    }
    bool operator>(const BigInt &v) const { return v < *this; }
    bool operator<=(const BigInt &v) const { return !(v < *this); }
    bool operator>=(const BigInt &v) const { return !(*this < v); }
    bool operator==(const BigInt &v) const { return num == v.num && neg == v.neg; }
    bool operator!=(const BigInt &v) const { return !(*this == v); }
    BigInt operator-() const
    {
        BigInt ret(*this);
        if (!ret.num.empty())
            ret.neg = !ret.neg;
        return ret;
    }
    BigInt &operator+=(const BigInt &x)
    {
        if (neg && !x.neg)
            return *this = x - (-*this);
        if (!neg && x.neg)
            return *this -= -x;
        assert(neg == x.neg);
        int maxs = max(num.size(), x.num.size());
        num.resize(maxs);
        int carry = 0;
        for (int i = 0; i < maxs; ++i)
        {
            int other = i >= x.num.size() ? 0 : x.num[i];
            num[i] += other + carry;
            carry = num[i] / BASE;
            num[i] %= BASE;
        }
        if (carry)
            num.push_back(carry);
        return *this;
    }
    /* O(len(x)). Assert *this >= x >= 0. */
    BigInt &subtract(const BigInt &x)
    {
        assert(!neg && !x.neg);
        int carry = 0;
        for (int i = 0; i < num.size(); ++i)
        {
            int other = i >= x.num.size() ? 0 : x.num[i];
            num[i] -= other + carry;
            carry = num[i] < 0;
            if (carry)
                num[i] += BASE;
        }
        trim();
        return *this;
    }
    BigInt &operator-=(const BigInt &x)
    {
        if (neg && !x.neg)
            return *this = -(-*this + x);
        if (x.neg)
            return *this += -x;
        assert(!neg && !x.neg);
        if (*this < x)
        {
            BigInt y = *this;
            *this = x;
            return *this = -subtract(y);
        }
        return subtract(x);
    }
    /* O(len(this)) + O(1) if |m|*BASE fits in ll.
    Fallbacks to BigInt multiplication if |m|*BASE doesn't fit in ll. */
    BigInt &operator*=(ll m)
    {
        const ll MX = LLONG_MAX / BASE;
        if (m < -MX || m > MX)
            return *this *= BigInt(m);
        neg ^= m < 0;
        m = abs(m);
        ll carry = 0;
        for (int i = 0; i < num.size(); ++i)
        {
            ll v = num[i] * m + carry;
            carry = v / BASE; // carry < m always.
            num[i] = v % BASE;
        }
        while (carry)
        {
            num.push_back(carry % BASE);
            carry /= BASE;
        }
        trim();
        return *this;
    }
    /* O(L log L) where L = len(this) + len(x) */
    BigInt &operator*=(const BigInt &x)
    {
        if (num.empty())
            return *this;
        neg ^= x.neg;
        auto c = fft::multiply(num, x.num);
        num.resize(c.size());
        ll carry = 0;
        for (int i = 0; i < c.size(); ++i)
        {
            c[i] += carry;
            carry = c[i] / BASE;
            num[i] = c[i] % BASE;
        }
        if (carry)
            num.push_back(carry);
        trim();
        return *this;
    }
    /* O(len(this)) if |d|*BASE fits in ll.
    Fallbacks to BigInt if |d|*BASE doesn't fit in ll. */
    ll divideAndRemainder(ll d)
    {
        assert(d != 0);
        const ll MX = LLONG_MAX / BASE;
        if (d < -MX || d > MX)
            return divideAndRemainder(BigInt(d)).val();
        bool wasNeg = neg;
        neg ^= d < 0;
        d = abs(d);
        ll cur = 0;
        vector<int> ret(num.size());
        for (int i = (int)num.size() - 1; i >= 0; --i)
        {
            cur *= BASE;
            cur += num[i];
            ret[i] = cur / d;
            cur %= d;
        }
        swap(num, ret);
        trim();
        return wasNeg ? -cur : cur;
    }
    BigInt &operator/=(ll v)
    {
        divideAndRemainder(v);
        return *this;
    }
    BigInt &operator%=(ll v)
    {
        ll remainder = divideAndRemainder(v);
        return *this = BigInt(remainder);
    }
    /* O(len(this) * len(b) * log2(BASE)) */
    BigInt divideAndRemainder(BigInt b)
    {
        assert(!b.num.empty());
        bool wasNeg = neg;
        neg ^= b.neg;
        b.neg = false;
        BigInt cur;
        vector<int> ret(num.size());
        for (int i = (int)num.size() - 1; i >= 0; --i)
        {
            cur *= BASE;
            cur += num[i];
            int lo = 0, hi = BASE - 1;
            while (lo < hi)
            {
                int d = (lo + hi + 1) >> 1;
                if (b * d > cur)
                    hi = d - 1;
                else
                    lo = d;
            }
            cur -= b * lo;
            ret[i] = lo;
        }
        swap(num, ret);
        trim();
        if (wasNeg && !cur.num.empty())
            cur.neg = true;
        return cur;
    }
    BigInt &operator/=(const BigInt &x)
    {
        divideAndRemainder(x);
        return *this;
    }
    BigInt &operator%=(const BigInt &x) { return *this = divideAndRemainder(x); }
    friend BigInt operator+(BigInt a, const BigInt &b) { return a += b; }
    friend BigInt operator-(BigInt a, const BigInt &b) { return a -= b; }
    friend BigInt operator*(ll a, BigInt b) { return b *= a; }
    friend BigInt operator*(BigInt a, ll b) { return a *= b; }
    friend BigInt operator*(BigInt a, const BigInt &b) { return a *= b; }
    friend BigInt operator/(BigInt a, ll b) { return a /= b; }
    friend BigInt operator/(BigInt a, const BigInt &b) { return a /= b; }
    friend BigInt operator%(BigInt a, ll b) { return a %= b; }
    friend BigInt operator%(BigInt a, const BigInt &b) { return a %= b; }
    BigInt &operator++() { return *this += 1; }
    BigInt &operator--() { return *this -= 1; }
    BigInt operator++(int)
    {
        BigInt ret(*this);
        *this += 1;
        return ret;
    }
    BigInt operator--(int)
    {
        BigInt ret(*this);
        *this -= 1;
        return ret;
    }
    /* If a = b = 0, returns 0. Else returns gcd of |a|, |b|.
    O(len(a)) if b = 0; else
    O(len(a) + log(|b|)) if |b|*BASE fits in ll; else
    O(len(a)*len(b)*log2(BASE) + log(|b|)). */
    friend BigInt gcd(const BigInt &a, ll b)
    {
        if (!b)
            return abs(a);
        ll r = abs(a % b).val();
        if (r == 0)
            return abs(BigInt(b));
        return __gcd(r, abs(b % r));
    }
    friend BigInt gcd(ll a, const BigInt &b) { return gcd(b, a); }
    /* If a = b = 0, returns 0. Else returns gcd of |a|, |b|.
    There are O(min(len(a),len(b)) iterations. After first 2 iterations, a',b'<=min(a,b).
    O(min(len(a),len(b))^3*log2(BASE) + len(a)*len(b)*log2(BASE)). */
    friend BigInt gcd(BigInt a, BigInt b)
    {
        a.neg = b.neg = false;
        while (!b.num.empty())
        {
            BigInt c(b);
            b = a % b;
            swap(a, c);
        }
        return a;
    }
    /* Get a random BigInt from [0, n-1] in expected O(2*len(n)). */
    friend BigInt randomBigInt(BigInt n)
    {
        static mt19937_64 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
        assert(!n.num.empty() && !n.neg);
        n--;
        for (;;)
        {
            BigInt res;
            res.num.resize(n.num.size());
            for (int i = (int)n.num.size() - 1; i >= 0; --i)
            {
                int mx = (i + 1 == n.num.size()) ? n.num[i] : BASE - 1;
                res.num[i] = rng() % (mx + 1);
            }
            res.trim();
            if (res <= n)
                return res;
        }
        assert(false);
    }
    friend BigInt abs(BigInt x)
    {
        x.neg = false;
        return x;
    }
    friend string to_string(const BigInt &x)
    {
        if (x.num.empty())
            return "0";
        string ret;
        if (x.neg)
            ret += '-';
        ret += to_string(x.num.back());
        string fmt = "%0" + to_string(BASE_DIGITS) + "d";
        for (int i = (int)x.num.size() - 2; i >= 0; --i)
        {
            char buf[BASE_DIGITS + 1];
            sprintf(buf, fmt.c_str(), x.num[i]);
            ret += buf;
        }
        return ret;
    }
    /* Throws if doesn't fit in ll. */
    ll val()
    {
        const unsigned long long MAX_ABS = LLONG_MAX + (unsigned ll)neg;
        const unsigned long long MX = MAX_ABS / BASE;
        unsigned long long ret = 0;
        for (int i = (int)num.size() - 1; i >= 0; --i)
        {
            if (ret > MX)
                throw;
            ret *= BASE;
            if (ret > MAX_ABS - num[i])
                throw;
            ret += num[i];
        }
        assert(ret <= MAX_ABS);
        return neg ? -ret : ret;
    }
    friend ostream &operator<<(ostream &os, const BigInt &x)
    {
        os << to_string(x);
        return os;
    }
};
BigInt operator""_x(const char *str)
{
    BigInt temp(str);
    return temp;
}
int main()
{
    BigInt val1, val2, val3;
    val1 = 14747474747474747474_x;
    val2 = 383747474747474747474_x;
    val3 = val1 * val2;
    cout << val3;
}