高精度加法
模板题链接：791. 高精度加法
1 // C = A + B, A >= 0, B >= 0 2 #include <iostream> 3 #include <vector> 4 #include <string> 5 using namespace std; 6 7 vector<int> add(vector<int> &a, vector<int> &b) { 8 vector<int> c; // c存放相加的结果 9 int t = 0; // t既表示进位，也表示每一位相加的结果 10 for (int i = 0; i < a.size() || i < b.size(); i++) { // i要小于a，b位数最大的那个 11 if (i < a.size()) t += a[i]; // 当i小于a的位数时才加a[i] 12 if (i < b.size()) t += b[i]; // 当i小于b的位数时才加b[i] 13 c.push_back(t % 10); // 把个位压入结果c中 14 t /= 10; // 这时t表示进位，如果t > 10给下一位进1，t < 10就进0 15 } 16 if (t) c.push_back(1); // 最后如果t == 1，这是来自上一位的进位，把t压入c中 17 18 return c; 19 } 20 21 int main() { 22 string sa, sb; 23 cin >> sa >> sb; 24 vector<int> a, b; 25 for (int i = sa.size() - 1; i >= 0; i--) { 26 a.push_back(sa[i] - '0'); 27 } 28 for (int i = sb.size() - 1; i >= 0; i--) { 29 b.push_back(sb[i] - '0'); 30 } 31 32 vector<int> c = add(a, b); 33 for (int i = c.size() - 1; i >= 0; i--) { 34 cout << c[i]; 35 } 36 37 return 0; 38 }
高精度减法
模板题链接：792. 高精度减法
1 // C = A - B, 满足A >= B, A >= 0, B >= 0 2 #include <iostream> 3 #include <vector> 4 #include <string> 5 using namespace std; 6 7 // 用于比较a和b的大小 8 bool cmp(vector<int> &a, vector<int> &b) { 9 if (a.size() != b.size()) return a.size() > b.size(); 10 for (int i = a.size() - 1; i >= 0; i--) { 11 if (a[i] != b[i]) return a[i] > b[i]; 12 } 13 return true; 14 } 15 16 // 下面的函数中保证a >= b 17 vector<int> sub(vector<int> &a, vector<int> &b) { 18 vector<int> c; // c存放相减的结果 19 int t = 0; // t既表示是否有借位，也表示每一位相减的结果 20 for (int i = 0; i < a.size(); i++) { 21 t = a[i] - t; 22 if (i < b.size()) t -= b[i]; // 当i小于b的位数才减去b[i]，否则不减 23 c.push_back((t + 10) % 10); // 因为t可能小于0或大于0，这种写法把两种情况都考虑了 24 if (t < 0) t = 1; // 最后这里t表示借位，如果t < 0，表示借了1位 25 else t = 0; // 否则就没借位 26 } 27 while (c.size() > 1 && c.back() == 0) { // 除去前导0 28 c.pop_back(); 29 } 30 31 return c; 32 } 33 34 int main() { 35 string sa, sb; 36 cin >> sa >> sb; 37 vector<int> a, b; 38 for (int i = sa.size() - 1; i >= 0; i--) { 39 a.push_back(sa[i] - '0'); 40 } 41 for (int i = sb.size() - 1; i >= 0; i--) { 42 b.push_back(sb[i] - '0'); 43 } 44 45 vector<int> c; 46 if (cmp(a, b)) { 47 c = sub(a, b); // 如果a >= b，直接传入a，b 48 } 49 else { 50 c = sub(b, a); // 如果b > a，则传入b，a，因为保证sub(a, b)参数中的a >= b 51 cout << "-"; 52 } 53 for (int i = c.size() - 1; i >= 0; i--) { 54 cout << c[i]; 55 } 56 57 return 0; 58 }
高精度乘低精度
模板题链接：793. 高精度乘法
原理大概如下图：
1 // C = A * b, A >= 0, b > 0 2 #include <iostream> 3 #include <vector> 4 #include <string> 5 using namespace std; 6 7 vector<int> mult(vector<int> &a, int b) { 8 vector<int> c; // c存放相乘的结果 9 int t = 0; // t既表示是否有进位，也表示每一位相乘的结果 10 for (int i = 0; i < a.size(); i++) { 11 t += a[i] * b; 12 c.push_back(t % 10); // 把个位压入c中 13 t /= 10; // 把个位去掉，表示进位 14 } 15 while (t) { 16 c.push_back(t % 10); // t可能大于10，逐位压入c中 17 t /= 10; 18 } 19 while (c.size() > 1 && c.back() == 0) { 20 c.pop_back(); // 除去前导0 21 } 22 23 return c; 24 } 25 26 int main() { 27 string sa; 28 int b; 29 cin >> sa >> b; 30 vector<int> a; 31 for (int i = sa.size() - 1; i >= 0; i--) { 32 a.push_back(sa[i] - '0'); 33 } 34 35 vector<int> c = mult(a, b); 36 for (int i = c.size() - 1; i >= 0; i--) { 37 cout << c[i]; 38 } 39 40 return 0; 41 }
高精度除以低精度
模板题链接：794. 高精度除法
1 // A / b = C ... r, A >= 0, b > 0 2 #include <iostream> 3 #include <vector> 4 #include <string> 5 #include <algorithm> 6 using namespace std; 7 8 vector<int> div(vector<int> &a, int b, int &r) { 9 vector<int> c; // c存放的是相除后的商 10 for (int i = a.size() - 1; i >= 0; i--) { // 这里是从后往前遍历位数的 11 r = r * 10 + a[i]; // 把上一位的余数乘10再加上当前位a[i] 12 c.push_back(r / b); // 然后把相除的商压如c中 13 r %= b; // r为当前位的余数 14 } 15 16 reverse(c.begin(), c.end()); // 相除的结果是正好是从左往右顺序的，为了和前面的结果保持一致，所以把结果进行反转 17 while (c.size() > 1 && c.back() == 0) { 18 c.pop_back(); // 除去前导0 19 } 20 21 return c; 22 } 23 24 int main() { 25 string sa; 26 int b; 27 cin >> sa >> b; 28 vector<int> a; 29 for (int i = sa.size() - 1; i >= 0; i--) { 30 a.push_back(sa[i] - '0'); 31 } 32 33 int r = 0; // r表示余数 34 vector<int> c = div(a, b, r); 35 for (int i = c.size() - 1; i >= 0; i--) { 36 cout << c[i]; 37 } 38 cout << '\n' << r; 39 40 return 0; 41 }