Арифметикаи дароз
Арифметикаи дароз — ин маҷмӯи сохторҳои додаҳо ва алгоритмҳо мебошад, ки имкон медиҳанд ададҳои хеле калонтарро нисбат ба он чӣ дар навъҳои стандартии додаҳо ҷойгир кардан мумкин аст, коркард кунем. Якчанд навъи арифметикаи дарозро меорем.
Мо ададҳоро дар шакли 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);
}