Long Arithmetic
Long Arithmetic is a set of data structures and algorithms that allow processing much larger numbers than can fit in standard data types. Let us present several types of long arithmetic.
We will store numbers as vector<int>, in which each element is one digit of the number (in reverse order). For example, for we will store .
typedef vector<int> BigNum;
void output(const BigNum& v) {
for (int i = (int)v.size() - 1; i >= 0; i--) {
cout << v[i];
}
cout << "\n";
}
BigNum input(long long x) {
if (x == 0) {
return {0};
} else {
BigNum v;
while (x > 0) {
v.push_back(x % 10);
x /= 10;
}
return v;
}
}
BigNum normalize(const BigNum& x) {
auto res = x;
while (res.size() > 1 && res.back() == 0) {
res.pop_back();
}
return res;
}
BigNum sum(const BigNum& x, const BigNum& y) {
BigNum res(x.size() + y.size(), 0);
for (int i = 0; i < x.size(); i++) {
res[i] += x[i];
}
for (int i = 0; i < y.size(); i++) {
res[i] += y[i];
}
for (int i = 0; i + 1 < res.size(); i++) {
res[i + 1] += res[i] / 10;
res[i] %= 10;
}
return normalize(res);
}
// x >= y
BigNum subtract(const BigNum& x, const BigNum& y) {
BigNum res = x;
for (int i = 0; i < y.size(); i++) {
res[i] -= y[i];
}
for (int i = 0; i < res.size(); i++) {
if (res[i] < 0) {
res[i] += 10;
res[i + 1] -= 1;
}
}
return normalize(res);
}
BigNum multiplication(const BigNum& x, const BigNum& y) {
BigNum res(x.size() + y.size());
for (int i = 0; i < x.size(); i++) {
for (int j = 0; j < y.size(); j++) {
res[i + j] += x[i] * y[j];
}
}
for (int i = 0; i + 1 < res.size(); i++) {
res[i + 1] += res[i] / 10;
res[i] %= 10;
}
return normalize(res);
}