高精度加减乘模板

这是我将紫书上的高精度模板和 Menci 的高精度模板进行一定程度的修改得到的自己的板子。

其中要注意的是高精度减法需要均为正数，且大数减小数。如何比较大小？模板里面重载了 << 运算符，可以直接比较大小。

修改结构体中的 WIDTH 与 BASE 可以达到修改压位的位数的目的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
struct BigInt {
    static const int BASE = 10000;
    static const int WIDTH = 4;
    int s[10005], n;
    
    BigInt(long long num = 0) {*this = num;}
    BigInt operator = (long long num) {
        memset(s, 0, sizeof(s));
        n = 0;
        do{
            s[++n] = num % BASE;
            num /= BASE;
        } while(num > 0);
        return *this;
    }
    BigInt operator = (const string& str) {
        memset(s, 0, sizeof(s));
        n = 0;
        int x, len = (str.length() - 1) / WIDTH + 1;
        for(int i = 0; i < len; i++) {
            int end = str.length() - i * WIDTH;
            int start = max(0, end - WIDTH);
            sscanf(str.substr(start, end - start).c_str(), "%d", &x);
            s[++n] = x;
        }
        return *this;
    }
    BigInt operator + (const BigInt& b) const {
        BigInt c;
        memset(c.s, 0, sizeof(c.s));
        c.n = 0;
        for(int i = 1, g = 0; ; i++) {
            if(g == 0 && i > n && i > b.n) break;
            int x = g;
            if(i <= n) x += s[i];
            if(i <= b.n) x += b.s[i];
            c.s[++c.n] = x % BASE;
            g = x / BASE;
        }
        return c;
    }
    BigInt operator * (const BigInt& b) const {
        BigInt c;
        memset(c.s, 0, sizeof(c.s));
        c.n = n + b.n;
        for(int i = 1; i <= n; i++) {
            for(int j = 1; j <= b.n; j++) {
                c.s[i + j - 1] += s[i] * b.s[j];
                c.s[i + j] += c.s[i + j - 1] / BASE;
                c.s[i + j - 1] %= BASE;
            }
        }
        while(c.n > 1 && c.s[c.n] == 0) c.n--;
        return c;
    }
    BigInt operator - (const BigInt& b) const {
        BigInt c;
        memset(c.s, 0, sizeof(c.s));
        c.n = 0;
        bool flag = false;
        for(int i = 1; i <= n; i++) {
            int x = s[i];
            if(i <= b.n) x -= b.s[i];
            if(flag) x--, flag = false;
            if(x < 0) x += BASE, flag = true;
            c.s[++c.n] = x;
        }
        while(c.n > 1 && c.s[c.n] == 0) c.n--;
        return c;
    }
    bool operator < (const BigInt& b) const {
        if(n != b.n) return n < b.n;
        for(int i = n; i >= 1; i--)
            if(s[i] != b.s[i]) return s[i] < b.s[i];
        return false;
    }
};

ostream& operator << (ostream& out, const BigInt& x) {
    out << x.s[x.n];
    for(int i = x.n - 1; i >= 1; i--) {
        out << setw(4) << setfill('0') << x.s[i];
    }
    return out;
}

istream& operator >> (istream& in, BigInt& x) {
    string s;
    if(!(in >> s)) return in;
    x = s;
    return in;
}