-
Notifications
You must be signed in to change notification settings - Fork 0
/
big_integer.cpp
87 lines (77 loc) · 1.93 KB
/
big_integer.cpp
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
struct BigInteger {
const int b = 1000000000;
vector<int> dig = {0};
BigInteger() {}
BigInteger(vector<int> a) {
dig = a;
if (dig.empty() || dig.back() != 0)
dig.push_back(0);
}
BigInteger(int a) {
dig.clear();
while (a) {
dig.push_back(a % b);
a /= b;
}
dig.push_back(0);
}
void operator=(BigInteger a) { dig = a.dig; }
BigInteger operator+(const BigInteger& other) const {
vector<int> ans = dig;
bool carry = false;
for (size_t i = 0; i < other.dig.size(); i++) {
if (i == ans.size()) {
ans.push_back(0);
}
if (carry) {
++ans[i];
}
carry = ans[i] + other.dig[i] >= b;
ans[i] = (ans[i] + other.dig[i]) % b;
}
if (carry)
ans.push_back(1);
return BigInteger(ans);
}
BigInteger operator*(const BigInteger& a) const {
vector<int> ans = vector<int>(a.dig.size() + dig.size(), 0);
for (size_t i = 0; i < dig.size(); i++)
for (size_t j = 0; j < a.dig.size(); j++)
ans[i + j] += dig[i] * a.dig[j];
int carry = 0;
for (size_t i = 0; i < ans.size(); i++) {
ans[i] += carry;
carry = ans[i] / b;
ans[i] %= b;
}
assert(carry == 0);
while (ans.size() >= 2 && ans.back() == 0 && ans[ans.size() - 2] == 0)
ans.pop_back();
return ans;
}
bool operator<(const BigInteger& a) const {
if (a.dig.size() < dig.size())
return 0;
else if (dig.size() < a.dig.size())
return 1;
for (int i = dig.size() - 1; i >= 0; i--)
if (dig[i] > a.dig[i])
return 0;
else if (dig[i] < a.dig[i])
return 1;
return 0;
}
friend ostream& operator<<(ostream& o, const BigInteger& num) {
bool leading_zeroes = true;
for (auto it = num.dig.rbegin(); it != num.dig.rend(); ++it) {
if ((*it) != 0) {
leading_zeroes = false;
}
if (leading_zeroes && (*it) == 0) {
continue;
}
o << (*it);
}
return o;
}
};