Длинная Арифметика
Длинная Арифметика - это набор структур данных и алгоритмов, позволяющих обрабатывать гораздо большие числа, чем можно уместить в стандартных типах данных. Приведем несколько типов длинной арифметики.
Мы будем хранить числа в виде vector<int>, в котором каждый элемент - это одна цифра числа (в обратном порядке). Например, для мы будем хранить .
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);
}