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
| struct BigNumber : public std::vector<int> {
BigNumber() {}
BigNumber(std::vector<int> a) { *this = a; }
BigNumber(std::initializer_list<int> a) { *this = a; }
BigNumber(std::size_t size) : std::vector<int>(size) {}
void init(LL x) { while (x) push_back(x % 10), x /= 10; if (empty()) *this = {0}; }
friend BigNumber operator +(BigNumber a, BigNumber b) {
BigNumber res(std::max(a.size(), b.size()) + 1);
for (std::size_t i = 0, t = 0; i < res.size(); ++ i)
t += (i < a.size() ? a[i] : 0) + (i < b.size() ? b[i] : 0),
res[i] = t % 10, t /= 10;
while (res.size() > 1 && !res.back()) res.pop_back();
return res;
}
friend bool operator <(BigNumber a, BigNumber b) {
if (a.size() ^ b.size()) return a.size() < b.size();
for (std::size_t i = a.size() - 1; ~i; -- i)
if (a[i] ^ b[i]) return a[i] < b[i];
return false;
}
friend bool operator <=(BigNumber a, BigNumber b) { return a < b || a == b; }
friend bool operator >(BigNumber a, BigNumber b) { return !(a <= b); }
friend BigNumber operator -(BigNumber a, BigNumber b) {
if (a == b) return {0};
assert(a > b);
BigNumber res(a.size());
int t = 0;
for (std::size_t i = 0; i < a.size(); ++ i)
t += a[i] - (i < b.size() ? b[i] : 0) + 10, res[i] = t % 10, t = t / 10 - 1;
assert(!t);
while (!res.back()) res.pop_back();
return res;
}
LL operator %(LL m) const {
LL res = 0;
for (std::size_t i = size() - 1; ~i; -- i)
res = (res + this->operator[](i)) % m;
return res;
}
friend std::istream& operator >>(std::istream &fin, BigNumber &a) {
std::string s;
fin >> s;
a.reserve(s.size());
for (std::size_t i = s.size() - 1; ~i; -- i) a.push_back(s[i] & 15);
return fin;
}
friend std::ostream& operator <<(std::ostream &fout, BigNumber a) {
std::string s;
s.reserve(a.size());
for (std::size_t i = s.size() - 1; ~i; -- i) s.push_back(a[i] | 48);
return fout << s;
}
};
|