【数学】高精度整数

struct BigInt {

    static const int BASE = 1000000000;
    static const int DLEN = 9;
    int len;
    vector<int> a;

    BigInt(int v = 0) {
        len = 0, a.resize(2);
        do {
            a[len++] = v % BASE;
            v /= BASE;
        } while(v);
    }

    BigInt(char *s) {
        int sl = strlen(s + 1);
        len = (sl + DLEN - 1) / DLEN, a.resize(len + 1), len = 0;
        for(int i = sl; i >= 1; i -= DLEN) {
            int tmp = 0, bj = i - DLEN + 1;
            for(int j = max(1, bj); j <= i; ++j)
                tmp = tmp * 10 + s[j] - '0';
            a[len++] = tmp;
        }
    }

    void maintain() {
        while(len > 1 && a[len - 1] == 0)
            --len;
    }

    BigInt operator+(const int &b)const {
        BigInt res;
        res.len = len + 1, res.a.resize(res.len + 1);
        for(int i = 0; i < len; ++i) {
            int tmp = res.a[i] + a[i] + (i == 0 ? b : 0);
            res.a[i + 1] += tmp / BASE, res.a[i] = tmp % BASE;
        }
        res.maintain();
        return move(res);
    }

    BigInt operator+(const BigInt &b)const {
        BigInt res;
        res.len = max(len, b.len) + 1, res.a.resize(res.len + 1);
        for(int i = 0; i < res.len; ++i) {
            int tmp = res.a[i] + ((i < len) ? a[i] : 0) + ((i < b.len) ? b.a[i] : 0);
            res.a[i + 1] += tmp / BASE, res.a[i] = tmp % BASE;
        }
        res.maintain();
        return move(res);
    }

    BigInt operator*(const int &b)const {
        BigInt res;
        res.len = len + 1, res.a.resize(res.len + 1);
        for(int i = 0; i < len; i++) {
            ll tmp = res.a[i] + 1LL * a[i] * b;
            res.a[i + 1] += tmp / BASE, res.a[i] = tmp % BASE;
        }
        res.maintain();
        return move(res);
    }

    BigInt operator*(const BigInt &b)const {
        BigInt res;
        res.len = len + b.len, res.a.resize(res.len + 1);
        for(int i = 0; i < len; i++) {
            for(int j = 0; j < b.len; j++) {
                ll tmp = res.a[i + j] + 1LL * a[i] * b.a[j];
                res.a[i + j + 1] += tmp / BASE, res.a[i + j] = tmp % BASE;
            }
        }
        res.maintain();
        return move(res);
    }

    int compare(const BigInt &b)const {
        if(len != b.len)
            return (len < b.len) ? -1 : 1;
        for(int i = len - 1; i >= 0; --i) {
            if(a[i] != b.a[i])
                return (a[i] < b.a[i]) ? -1 : 1;
        }
        return 0;
    }

    bool operator<(const BigInt &b)const {
        return compare(b) == -1;
    }

    bool operator==(const BigInt &b)const {
        return compare(b) == 0;
    }

    bool operator>(const BigInt &b)const {
        return compare(b) == 1;
    }

    void print() {
//        assert(BASE == 1000000000 && DLEN == 9);
        printf("%d", a[len - 1]);
        for(int i = len - 2; i >= 0 ; --i)
            printf("%09d", a[i]);
        printf("
");
    }

};