模板 - 高精度整数（新）

老版本（kuangbin）那个浪费空间还慢。
把每一位改成极限的9位就是最快的。

struct BigInt {
    const static int BASE = 1000000000;
    vector<int> a;
    int len;

    BigInt() {
        a.resize(4);
        len = 1;
    }

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

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

    BigInt operator *(const BigInt &b)const {
        //高精乘高精，考虑用FFT优化
        BigInt res;
        res.a.resize(len + b.len);
        for(int i = 0; i < len; i++) {
            int up = 0;
            for(int j = 0; j < b.len; j++) {
                ll temp = 1ll * a[i] * b.a[j] + res.a[i + j] + up;
                res.a[i + j] = temp % BASE;
                up = temp / BASE;
            }
            if(up != 0)
                res.a[i + b.len] = up;
        }
        res.len = len + b.len;
        while(res.a[res.len - 1] == 0 && res.len > 1)
            res.len--;
        return res;
    }

    BigInt operator *(const int &b)const {
        //高精乘低精
        BigInt res;
        res.a.resize(len + 1);
        for(int i = 0; i < len; i++) {
            int up = 0;
            ll temp = 1ll * a[i] * b + res.a[i] + up;
            res.a[i] = temp % BASE;
            up = temp / BASE;
            if(up != 0)
                res.a[i + 1] = up;
        }
        res.len = len + 1;
        while(res.a[res.len - 1] == 0 && res.len > 1)
            res.len--;
        return res;
    }

    bool operator <(const BigInt &b)const {
        if(len != b.len)
            return len < b.len;
        else {
            for(int ln = len - 1; ln >= 0; ln--) {
                if(a[ln] != b.a[ln])
                    return a[ln] < b.a[ln];
            }
            return false;
        }
    }

    void output() {
        printf("%d",a[len - 1]);
        for(int i = len - 2; i >= 0 ; i--)
            printf("%09d",a[i]);
        printf("n");
    }
};