除了除法我们都应该将倒过来，因为要进行进位或借位
比较大小先比较长度，长度相等字典序就是其大小
加法倒序相加，记得保存进位
减法倒序相减，借1为10，⚠️大减小，去除前导0
乘法直接算到当前微商，去除前导0
除法比较困难，可以满足列除法式子时进行减法，最后也减9次，注意这个0的处理，比较复杂
应该注释还算清楚，适合有一定水平的入门者。基础设计来源于crq
#include <bits/stdc++.h> using namespace std; const int N = 1e5 + 5; int a[N], b[N], c[N]; //字符串类型转换为数组，并且倒过来 void stringToArr(string s, int a[]) { int len = s.length(); //倒过来进行赋值 for (int i = 0; i < len; i++) { a[i] = s[len - i - 1] - '0'; } } //初始化字符串转换为数组 void init(string s1, string s2) { //清0,全局变量只有第一次是0 memset(a, 0, sizeof(a)); memset(b, 0, sizeof(b)); //将其转为数字串，并倒过来 stringToArr(s1, a); stringToArr(s2, b); } //数组转换为字符串，并且倒过来 string arrToString(int a[], int n) { string s = ""; //倒过来进行字符的还原 for (int i = n - 1; i >= 0; i--) { s += (char)(a[i] + '0'); } return s; } //两数比较，大于等于返回true bool cmp(string a, string b) { //位数不等，位数大的数大 if (a.length() != b.length()) { return a.length() > b.length(); } //位数相等字典序大小即大小关系 return a >= b; } //加法 string add(string s1, string s2) { //先把s1和s2初始化到ab数组里 init(s1, s2); //长度为两数最大的那个数 int len = max(s1.length(), s2.length()); //进位 int step = 0; for (int i = 0; i < len; i++) { //当前位就是两数相加及进位的个位 c[i] = (a[i] + b[i] + step) % 10; //当前位就是两数相加及进位的十位 step = (a[i] + b[i] + step) / 10; } //进位不为0，所以要多一位 if (step != 0) c[len++] = step; return arrToString(c, len); } //减法，只能大减小 string sub(string s1, string s2) { //先把s1和s2初始化到ab数组里 init(s1, s2); for (int i = 0; i < s1.length(); i++) { //小于就借位 if (a[i] < b[i]) { a[i] += 10; a[i + 1]--; } //进行除法 c[i] = a[i] - b[i]; } //s1是大数，所以他的长度就是ans的长度 int m = s1.length(); //去除前导0 while (m > 0 && c[m - 1] == 0)m--; //相等结果为0要返回0 if (m == 0)return "0"; //把c数组转换为string类型输出，m作为位数传递 return arrToString(c, m); } //乘法 string mul(string s1, string s2) { //先把s1和s2初始化到ab数组里 init(s1, s2); for (int j = 0, i; j < s2.length(); j++) { //进位为step int step = 0; for (i = 0; i < s1.length(); i++) { //就是列乘法计算，直接加进去目标位 c[i + j] += a[i] * b[j] + step; //有可能产生进位，需要保存 step = c[i + j] / 10; //目标位是一位数 c[i + j] = c[i + j] % 10; } //最终进位还是空的，直接给进位吧 c[i + j] = step; } //最终可能有两个总长的位数 int m = s1.length() + s2.length(); //去除前导0 while (m > 1 && c[m - 1] == 0)m--; return arrToString(c, m); } //除法，返回余数，c是商 string div(string a, string b, string &c) { //remainder的缩写，代表余数，也就是当前的被除数 string rem = ""; //c有可能会被操作了，清空一下 c = ""; for (int i = 0; i < a.length(); i++) { //余数为0，就是当前一位。否则加上当前位 if (rem == "0")rem = a[i]; else rem = rem + a[i]; int t = 0; //如果被除数比除数大，进行减法，t最大也是9 while (cmp(rem, b)) { rem = sub(rem, b); t++; } //c还是空且t是0，直接进行下一次循环，解决了商的前导0 if (c == "" && t == 0)continue; //商加上求出的当前位 c = c + char(t + '0'); } return rem; } int main() { string a,b,c; while(cin >> a >> b) { //加法 cout << add(a,b) << " "; //减法 cout << sub(a,b) << " "; //乘法 cout << mul(a,b) << " "; //除法使用，依次输出商和余数 string d = div(a, b, c); cout << c << " " << d << " "; } return 0; }
以上乘法的复杂度还是不是太满意(是n*m的)，我们可以用fft来做
把每一项作为系数进行fft，这个范围我竟然算错了，是2097152要大于所以是2.1e6，2e6就一直RE。代码可以通过https://www.luogu.com.cn/problem/P1919
优雅的fft高精度
#include <bits/stdc++.h> using namespace std; const int N = 2.1e6; const double Pi = acos(-1); int n, m, r[N], P, ans[N]; struct C { double x, y; } a[N], b[N]; C operator+(C a, C b) { return (C){a.x + b.x, a.y + b.y}; } C operator-(C a, C b) { return (C){a.x - b.x, a.y - b.y}; } C operator*(C a, C b) { return (C){a.x * b.x - a.y * b.y, a.x * b.y + b.x * a.y}; } void FFT(C f[], int opt) { for (int i = 0; i < n; ++i) if (i < r[i]) swap(f[i], f[r[i]]); for (int len = 1, nl = 2; len < n; len = nl, nl <<= 1) { C rot = (C){cos(Pi / len), opt * sin(Pi / len)}; for (int l = 0; l < n; l += nl) { C w = (C){1, 0}; int r = l + len; for (int k = l; k < r; ++k, w = w * rot) { C x = f[k], y = w * f[k + len]; f[k] = x + y, f[k + len] = x - y; } } } } string arrToString(int a[], int n) { string s = ""; while (n > 1 && a[n - 1] == 0) n--; for (int i = n - 1; i >= 0; i--) { s += (char)(a[i] + '0'); } return s; } void stringToArr(string s, C a[]) { int len = s.length(); for (int i = 0; i < len; i++) { a[i].x = s[len - i - 1] - '0'; } } int main() { string s, c; cin >> s; stringToArr(s, a); cin >> c; stringToArr(c, b); n = max(s.length(), c.length()); for (m = n + n, n = 1; n <= m; n <<= 1, ++P) ; for (int i = 0; i < n; ++i) r[i] = (r[i >> 1] >> 1) | ((i & 1) << (P - 1)); //蝴蝶变换FFT FFT(a, 1), FFT(b, 1); for (int i = 0; i < n; ++i) a[i] = a[i] * b[i]; FFT(a, -1); for (int i = 0; i <= m; ++i) ans[i] = (int)(a[i].x / n + .5); for (int i = 0, tmp1, tmp2; i < m; ++i) ans[i + 1] += (ans[i] / 10), ans[i] %= 10; cout << arrToString(ans, m + 1) << " "; }