大数运算(细节注释)
#include <bits/stdc++.h>
using namespace std;
int compare(vector<int>& A, vector<int>& B) {
if (A.size() > B.size()) return 1;
if (A.size() < B.size()) return -1;
for (int i = A.size() - 1; i >= 0; i--) {
if (A[i] > B[i]) return 1;
if (A[i] < B[i]) return -1;
}
return 0;
}
// 加法
vector<int> add(vector<int>& A, vector<int>& B) {
vector<int> C;
for (int i = 0, t = 0; i < A.size() || i < B.size() || t/*t保证了有进位的时候不漏,并且不会产生前置0*/; i++) {
if (i < A.size()) t += A[i];
if (i < B.size()) t += B[i];
C.push_back(t % 10);
t /= 10;
}
return C;
}
// 减法:传入的A > B
vector<int> sub(vector<int>& A, vector<int>& B) {
vector<int> C;
for (int i = 0, t = 0; i < A.size(); i++) {
t += A[i];
if (i < B.size()) t -= B[i];
C.push_back((t + 10) % 10); // 利用 t在前置条件下必定在[-9, 9]范围内 这一点
if (t < 0) t = -1; // 需要向前借位
else t = 0; // 不需要借位
}
// 把前置0去掉:注意,要保留最后一个0
while (C.size() > 1 && C.back() == 0) C.pop_back();
return C;
}
//乘法:
vector<int> mul(vector<int>& A, vector<int>& B) {
// (10^n - 1) * (10^m - 1) < 10^(n + m)
// 所以n位数乘m位数的结果必定小于n + m位
int n = A.size(), m = B.size();
vector<int> C(n + m);
// 先存每两位乘积对C[i]的贡献
for (int i = 0; i < A.size(); i++) {
for (int j = 0; j < B.size(); j++) {
C[i + j] += A[i] * B[j]; // 如何证明C[i + j]不会爆掉int呢?
}
}
// 处理C[i]
for (int i = 0, t = 0; i < n + m; i++) {
t += C[i];
C[i] = t % 10;
t /= 10;
}
// 因为一直遍历到n + m - 1, 所以除了吃满不然都会有前置0
while (C.size() > 1 && C.back() == 0) C.pop_back();
return C;
}
// 打印结果
void print(vector<int> A) {
for (int i = A.size() - 1; i >= 0; i--) cout << A[i];
cout << endl;
}
int main() {
string a, b;
cin >> a >> b;
int na = 1, nb = 1; //记录a、b的正负
// 预处理:去除符号
if (a[0] == '-') na = -1, a = a.substr(1);
if (b[0] == '-') nb = -1, b = b.substr(1);
vector<int> A, B; // A、B先存低位再存高位
for (int i = a.size() - 1; i >= 0; i--) A.push_back(a[i] - '0');
for (int i = b.size() - 1; i >= 0; i--) B.push_back(b[i] - '0');
// 分两种情况处理: 同号 不同号
if (na * nb > 0) {
// 加法
if (na < 0) cout << '-';
print(add(A, B));
// 减法
bool has_swap = false;
if (compare(A, B) < 0) {
has_swap = true;
swap(A, B);
}
auto C = sub(A, B);
// 输出负号的条件:A 比 B小
// 注意情况:不要输出-0
if (na < 0 && !has_swap || na > 0 && has_swap) {
if (C.size() > 1 || C[0] > 0) {
cout << '-';
}
}
print(C);
// 乘法
print(mul(A, B));
} else {
// 加法
// 异号情况下相当于减法
bool has_swap = false;
if (compare(A, B) < 0) {
has_swap = true;
swap(A, B);
swap(na, nb);
}
auto C = sub(A, B);
// 输出负号的条件是,绝对值大的那个是负号
if (na < 0 && (C.size() > 1 || C[0] > 0)) cout << '-';
print(C);
// 减法
if (na > 0 && has_swap || na < 0 && !has_swap) cout << '-';
print(add(A, B));
// 乘法
if (a != "0" && b != "0") cout << '-';
print(mul(A, B));
}
return 0;
}