Star's Blog

1
#include <iostream>
2
#include <vector>
3
#include <cmath>
4
using namespace std;
5

6
class Hipre {
7
    vector<int> a;
8

9
public:
10
    void mv(int t) {
11
        vector<int> b(t, 0);
12
        b.insert(b.end(), a.begin(), a.end());
13
        a = b;
14
    }
15
    Hipre() {
16
        a = vector<int>(1, 0);
17
    }
18

19
    Hipre(int n) {
20
        if (!n) {
21
            a = vector<int>(1, 0);
22
        }
23
        else
24
            while (n) {
25
                a.push_back(n % 10);
26
                n /= 10;
27
            }
28
    }
29

30
    int length() const {
31
        return a.size();
32
    }
33

34
    int to_int() {
35
        int res = 0, mul = 1;
36
        for (int i = 0; i < a.size(); ++i) {
37
            res += a[i] * mul;
38
            mul *= 10;
39
        }
40
        return res;
41
    }
42

43
    int &operator [](const int &p) {
44
        return a[p];
45
    }
46

47
    friend istream &operator >>(istream &cin, Hipre &a) {
48
        static string s;
49
        cin >> s;
50
        a.a = vector<int>(s.length());
51
        for (int i = 0; i < s.length(); ++i) {
52
            a.a[i] = s[s.length() - i - 1] - 48;
53
        }
54
        while (a.length() > 1 && a.a.back() == 0) a.a.pop_back();
55
        return cin;
56
    }
57

58
    friend ostream &operator <<(ostream &cout, const Hipre &a) {
59
        for (int i = a.length() - 1; i >= 0; --i)
60
            cout << a.a[i];
61
        return cout;
62
    }
63

64
    bool operator <(const Hipre &c) const {
65
        if (length() != c.length()) return length() < c.length();
66
        else {
67
            for (int i = length() - 1; i >= 0; --i) {
68
                if (a[i] != c.a[i]) return a[i] < c.a[i];
69
            }
70
            return false;
71
        }
72
    }
73

74
    bool operator ==(const Hipre &c) const {
75
        if (length() != c.length()) return false;
76
        else {
77
            for (int i = length() - 1; i >= 0; --i) {
78
                if (a[i] != c.a[i]) return false;
79
            }
80
            return true;
81
        }
82
    }
83

84
    Hipre operator +(const Hipre &c) {
85
        auto &b = c.a;
86
        Hipre res;
87
        res.a = vector<int>(max(a.size(), b.size()) + 1, 0);
88
        for (int i = 0; i < res.length(); ++i) {
89
            if (i < a.size() && i < b.size()) res[i] += a[i] + b[i];
90
            else if (i < a.size()) res[i] += a[i];
91
            else if (i < b.size()) res[i] += b[i];
92
            if (res[i] > 9) res.a[i + 1] += 1, res[i] -= 10;
93
        }
94
        while (res.length() > 1 && res.a.back() == 0) res.a.pop_back();
95
        return res;
96
    }
97

98
    Hipre operator -(const Hipre &c) {
99
        Hipre res = *this;
100
        for (int i = 0; i < res.length(); ++i) {
101
            if (i < c.length()) res[i] -= c.a[i];
102
            if (res[i] < 0) res[i] += 10, res.a[i + 1] -= 1;
103
        }
104
        while (res.length() > 1 && res.a.back() == 0) res.a.pop_back();
105
        return res;
106
    }
107

108
    Hipre operator *(const Hipre &c) {
109
        auto &b = c.a;
110
        Hipre res;
111
        res.a = vector<int>(a.size() + b.size(), 0);
112
        for (int i = 0; i < a.size(); ++i) {
113
            for (int j = 0; j < b.size(); ++j) {
114
                res.a[i + j] += a[i] * b[j];
115
            }
116
        }
117
        for (int i = 0; i < res.length() - 1; ++i) {
118
            res.a[i + 1] += res[i] / 10;
119
            res[i] %= 10;
120
        }
121
        while (res.length() > 1 && res.a.back() == 0) res.a.pop_back();
122
        return res;
123
    }
124

125
    Hipre operator *=(const int &c) {
126
        if (c)
127
            a.resize(a.size() + (int)floor(log10(c)) + 1);
128
        for (int i = 0; i < a.size(); ++i) {
129
            a[i] *= c;
130
        }
131
        for (int i = 0; i < a.size() - 1; ++i) {
132
            if (a[i] > 9) a[i + 1] += a[i] / 10, a[i] %= 10;
133
        }
134
        while (a.size() > 1 && a.back() == 0) a.pop_back();
135
        return *this;
136
    }
137

138
    Hipre operator *(const int &c) {
139
        Hipre t = *this;
140
        return t *= c;
141
    }
142

143
    Hipre operator /(const int &c) {
144
        Hipre res;
145
        res.a = vector<int>(a.size());
146
        int t = 0;
147
        for (int i = a.size() - 1; i >= 0; --i) {
148
            t = t * 10 + a[i];
149
            if (t >= c) res[i] = t / c;
150
            t %= c;
151
        }
152
        while (res.length() > 1 && res.a.back() == 0) res.a.pop_back();
153
        return res;
154
    }
155

156
    Hipre operator /(Hipre c) {
157
        Hipre res, b = *this;
158
        int l = b.length() - c.length();
159
        res.a = vector<int>(l + 1, 0);
160
        c.mv(b.length() - c.length());
161
        for (int i = l; i >= 0; --i) {
162
            while (!(b < c)) {
163
                b = b - c;
164
                res[i]++;
165
            }
166
            c.a.erase(c.a.begin());
167
        }
168
        while (res.length() > 1 && res.a.back() == 0) res.a.pop_back();
169
        return res;
170
    }
171

172
    Hipre operator %(Hipre c) {
173
        Hipre b = *this;
174
        int l = b.length() - c.length();
175
        c.mv(b.length() - c.length());
176
        for (int i = l; i >= 0; --i) {
177
            while (!(b < c)) {
178
                b = b - c;
179
            }
180
            c.a.erase(c.a.begin());
181
        }
182
        while (b.length() > 1 && b.a.back() == 0) b.a.pop_back();
183
        return b;
184
    }
185
};
186

187
int main() {
188
    ios::sync_with_stdio(0);
189
    cin.tie(0), cout.tie(0);
190
    Hipre a, b;
191
    cin >> a >> b;
192
    cout << a / b << endl;
193
    return 0;
194
}