高精度问题描述:
// C = A + B, A >= 0, B >= 0 vector<int> add(vector<int> &A, vector<int> &B) { if (A.size() < B.size()) return add(B, A); //始终保证位数大的数在前面,这样后面每次for循环都遍历位数长的那个 vector<int> C; int t = 0;//进位,初始为0 for (int i = 0; i < A.size(); i ++ ) { t += A[i]; if (i < B.size()) t += B[i]; C.push_back(t % 10); t /= 10; } if (t) C.push_back(t); //处理最高位的进位 return C; } 作者:yxc 链接:https://www.acwing.com/blog/content/277/ 来源:AcWing
// C = A - B, 满足A >= B, A >= 0, B >= 0 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] - t; //t为借位标志 if (i < B.size()) t -= B[i]; C.push_back((t + 10) % 10); //把两种情况合在一起了 if (t < 0) t = 1; //t<0表示需要借位 else t = 0; } while (C.size() > 1 && C.back() == 0) C.pop_back(); //去除前导0 return C; } 作者:yxc 链接:https://www.acwing.com/blog/content/277/ 来源:AcWing
// C = A * b, A >= 0, b >= 0 vector<int> mul(vector<int> &A, int b) { vector<int> C; int t = 0; for (int i = 0; i < A.size() || t; i ++ ) { if (i < A.size()) t += A[i] * b; C.push_back(t % 10); t /= 10; } while (C.size() > 1 && C.back() == 0) C.pop_back();//去除前导0 return C; } 作者:yxc 链接:https://www.acwing.com/blog/content/277/ 来源:AcWing
// A / b = C ... r, A >= 0, b > 0 vector<int> div(vector<int> &A, int b, int &r) { vector<int> C; r = 0; for (int i = A.size() - 1; i >= 0; i -- ) { r = r * 10 + A[i]; C.push_back(r / b); r %= b; } reverse(C.begin(), C.end()); //逆序一下 while (C.size() > 1 && C.back() == 0) C.pop_back(); return C; } 作者:yxc 链接:https://www.acwing.com/blog/content/277/ 来源:AcWing