Bignum(Vector)

/// Bignum với vector<>
/// M là số chữ số ước lượng, nhớ thay đổi với các bài
/// Nếu không có phép nhân thì nên đẩy BASE lên 1e17 hoặc 1e18
/// a = Bignum(5) || a = Bignum("5") đều được, tuy nhiên khuyến khích dùng loại 1
/// cin >> a hay a.read() đều được
/// cout << a hay a.print() đều được, khuyến khích dùng loại 1
/// Phép chia và phép mod chỉ dùng cho số nguyên và cho ra kết quả nguyên
/// Phép nhân fft


using cd = complex<long double>;
const double PI = acos(-1);
const int M = 64;
const ll BASE = 1e7;
const int gd = log10(BASE);
const int maxn = M / gd + 1;
struct Bignum
{
    vector<ll> a;
    Bignum(ll x = 0)
    {
        a.reserve(maxn);
        do
        {
            a.emplace_back(x % BASE);
            x /= BASE;
        } while (x);
    }
    Bignum(const string &s)
    {
        Convert(s);
    }
    ll stoll(const string &s)
    {
        ll ans(0);
        for (auto i : s)
            ans = ans * 10 + i - '0';
        return ans;
    }
    void Convert(const string &s)
    {
        a.clear();
        a.reserve(maxn);
        for (int i = s.size() - 1; ~i; --i)
        {
            int j = max(0, i - gd + 1);
            a.emplace_back(stoll(s.substr(j, i - j + 1)));
            i = j;
        }
        fix();
    }
    void fix()
    {
        a.emplace_back(0);
        for (int i = 0; i < (int)a.size() - 1; ++i)
        {
            a[i + 1] += a[i] / BASE;
            a[i] %= BASE;
            if (a[i] < 0)
            {
                a[i] += BASE;
                --a[i + 1];
            }
        }
        while ((int)a.size() > 1 && a.back() == 0)
            a.pop_back();
    }
    Bignum &operator+=(const Bignum &x)
    {
        a.resize(max(a.size(), x.a.size()));
        for (int i = 0; i < (int)a.size(); ++i)
            a[i] += x.a[i];
        fix();
        return *this;
    }
    Bignum &operator-=(const Bignum &x)
    {
        a.resize(max(a.size(), x.a.size()));
        for (int i = 0; i < (int)x.a.size(); ++i)
            a[i] -= x.a[i];
        fix();
        return *this;
    }
    void fft(vector<cd> &a, bool invert)
    {
        int n = a.size();

        for (int i = 1, j = 0; i < n; i++)
        {
            int bit = n >> 1;
            for (; j & bit; bit >>= 1)
                j ^= bit;
            j ^= bit;

            if (i < j)
                swap(a[i], a[j]);
        }

        for (int len = 2; len <= n; len <<= 1)
        {
            long double ang = 2 * PI / len * (invert ? -1 : 1);
            cd wlen(cos(ang), sin(ang));
            for (int i = 0; i < n; i += len)
            {
                cd w(1);
                for (int j = 0; j < len / 2; j++)
                {
                    cd u = a[i + j], v = a[i + j + len / 2] * w;
                    a[i + j] = u + v;
                    a[i + j + len / 2] = u - v;
                    w *= wlen;
                }
            }
        }

        if (invert)
        {
            for (cd &x : a)
                x /= n;
        }
    }
    Bignum &operator*=(const Bignum &x)
    {
        int m = 1;
        while (m < (int)(a.size() + x.a.size()))
            m <<= 1;
        vector<cd> fa(m), fb(m);
        for (int i = 0; i < (int)a.size(); ++i)
            fa[i] = a[i];
        for (int i = 0; i < (int)x.a.size(); ++i)
            fb[i] = x.a[i];
        fft(fa, false); /// dft
        fft(fb, false); /// dft
        for (int i = 0; i < m; i++)
            fa[i] *= fb[i];
        fft(fa, true); ///Interpolation
        a.resize(m);
        for (int i = 0; i < (int)a.size(); ++i)
            a[i] = round(fa[i].real());
        fix();
        return *this;
    }
    Bignum &operator/=(const ll &x)
    {
        ll r = 0ll;
        for (int i = (int)a.size() - 1; ~i; --i)
        {
            r = r * BASE + a[i];
            a[i] = r / x;
            r %= x;
        }
        fix();
        return *this;
    }
    Bignum operator+(const Bignum &s)
    {
        Bignum c;
        c.a.resize(a.size());
        copy(a.begin(), a.end(), c.a.begin());
        c += s;
        return c;
    }
    Bignum operator-(const Bignum &s)
    {
        Bignum c;
        c.a.resize(a.size());
        copy(a.begin(), a.end(), c.a.begin());
        c -= s;
        return c;
    }
    Bignum operator*(const Bignum &s)
    {
        Bignum c;
        c.a.resize(a.size());
        copy(a.begin(), a.end(), c.a.begin());
        c *= s;
        return c;
    }
    Bignum operator/(const ll &x)
    {
        Bignum c;
        c.a.resize(a.size());
        copy(a.begin(), a.end(), c.a.begin());
        c /= x;
        return c;
    }
    ll operator%(const ll &x)
    {
        ll ans(0);
        for (int i = a.size() - 1; ~i; --i)
            ans = (ans * BASE + a[i]) % x;
        return ans;
    }
    int com(const Bignum &s) const
    {
        if (a.size() < s.a.size())
            return 1;
        if (a.size() > s.a.size())
            return 2;
        for (int i = a.size() - 1; ~i; --i)
            if (a[i] > s.a[i])
                return 2;
            else if (a[i] < s.a[i])
                return 1;
        return 3;
    }
    bool operator<(const Bignum &s) const
    {
        return com(s) == 1;
    }
    bool operator>(const Bignum &s) const
    {
        return com(s) == 2;
    }
    bool operator==(const Bignum &s) const
    {
        return com(s) == 3;
    }
    bool operator<=(const Bignum &s) const
    {
        return com(s) != 2;
    }
    bool operator>=(const Bignum &s) const
    {
        return com(s) != 1;
    }
    void read()
    {
        string s;
        cin >> s;
        Convert(s);
    }
    void print()
    {
        int i = a.size() - 1;
        cout << a[i];
        for (--i; ~i; --i)
            cout << setw(gd) << setfill('0') << a[i];
    }
    friend istream &operator>>(istream &in, Bignum &x)
    {
        string s;
        in >> s;
        x.Convert(s);
        return in;
    }
    friend ostream &operator<<(ostream &out, const Bignum &x)
    {
        int i = x.a.size() - 1;
        out << x.a[i];
        for (--i; ~i; --i)
            out << setw(gd) << setfill('0') << x.a[i];
        return out;
    }
};