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

template <size_t N>
struct BigInt {
    int a[N];
    BigInt(int x = 0) : a {} {
        for (int i = 0; x; i ++) {
            a[i] = x % 10;
            x /= 10;
        }
    }
    auto &operator*=(int x) {
        for (int i = 0; i < N; i ++) {
            a[i] *= x;
        }
        for (int i = 0; i < N - 1; i ++) {
            a[i + 1] += a[i] / 10;
            a[i] %= 10;
        }
        return *this;
    }

    auto &operator/=(int x) {
        for (int i = N - 1; i >= 0; i --) {
            if (i) {
                a[i - 1] += a[i] % x * 10;
            }
            a[i] /= x;
        }
        return *this;
    }

    auto &operator+=(const BigInt &x) {
        for (int i = 0; i < N; i ++) {
            a[i] += x.a[i];
            if (a[i] >= 10) {
                a[i + 1] += 1;
                a[i] -= 10;
            }
        }
        return *this;
    }

    auto operator<(const BigInt &x) {
        int l = N - 1;
        while (a[l] == 0)
            l --;
        int r = N - 1;
        while (x.a[r] == 0)
            r --;
        if (l > r)
            return false;
        if (l < r)
            return true;
        for (int i = l; i >= 0; i --) {
            if (a[i] > x.a[i])
                return false;
            if (a[i] < x.a[i])
                return true;
        }
        return false;
    }
};

template<size_t N>
auto &operator<<(ostream &o, const BigInt<N> &a) {
    int t = N - 1;
    while (a.a[t] == 0)
        t --;
    if (t < 0) {
        o << 0;
        return o;
    }
    for (int i = t; i >= 0; i --)
        o << a.a[i];
    return o;
}