高精度。。。

大位数运算问题高精度加法#include cstdio #include cstring constexpr int LEN 1004; int a[LEN], b[LEN], c[LEN]; void clear(int a[]) { for (int i 0; i LEN; i) a[i] 0; } void read(int a[]) { static char s[LEN 1]; scanf(%s, s); clear(a); int len strlen(s); for (int i 0; i len; i) a[len - i - 1] s[i] - 0; } void print(int a[]) { int i; for (i LEN - 1; i 1; --i) if (a[i] ! 0) break; for (; i 0; --i) putchar(a[i] 0); putchar(\n); } void add(int a[], int b[], int c[]) { clear(c); for (int i 0; i LEN - 1; i) { c[i] a[i] b[i]; if (c[i] 10) { c[i 1] 1; c[i] - 10; } } } int main() { read(a); read(b); add(a, b, c); print(c); return 0; }高精度减法#include cstdio #include cstring constexpr int LEN 1004; int a[LEN], b[LEN], c[LEN]; void clear(int a[]) { for (int i 0; i LEN; i) a[i] 0; } void read(int a[]) { static char s[LEN 1]; scanf(%s, s); clear(a); int len strlen(s); for (int i 0; i len; i) a[len - i - 1] s[i] - 0; } void print(int a[]) { int i; for (i LEN - 1; i 1; --i) if (a[i] ! 0) break; for (; i 0; --i) putchar(a[i] 0); putchar(\n); } bool cmp(int a[], int b[]) { for (int i LEN - 1; i 0; --i) { if (a[i] b[i]) return true; if (a[i] b[i]) return false; } return true; } void sub(int a[], int b[], int c[]) { clear(c); for (int i 0; i LEN - 1; i) { c[i] a[i] - b[i]; if (c[i] 0) { c[i 1] - 1; c[i] 10; } } } int main() { read(a); read(b); if (cmp(a, b)) { sub(a, b, c); print(c); } else { sub(b, a, c); putchar(-); print(c); } return 0; }高精度乘法高精度*低精度#include cstdio #include cstring constexpr int LEN 1004; int a[LEN], b[LEN], c[LEN]; void clear(int a[]) { for (int i 0; i LEN; i) a[i] 0; } void read(int a[]) { static char s[LEN 1]; scanf(%s, s); clear(a); int len strlen(s); for (int i 0; i len; i) a[len - i - 1] s[i] - 0; } void print(int a[]) { int i; for (i LEN - 1; i 1; --i) if (a[i] ! 0) break; for (; i 0; --i) putchar(a[i] 0); putchar(\n); } void mul_short(int a[], int b, int c[]) { clear(c); for (int i 0; i LEN - 1; i) { c[i] a[i] * b; if (c[i] 10) { c[i 1] c[i] / 10; c[i] % 10; } } } int main() { read(a); read(b); sub(a, b, c); print(c); return 0; }高精度*高精度#include cstdio #include cstring constexpr int LEN 1004; int a[LEN], b[LEN], c[LEN]; void clear(int a[]) { for (int i 0; i LEN; i) a[i] 0; } void read(int a[]) { static char s[LEN 1]; scanf(%s, s); clear(a); int len strlen(s); for (int i 0; i len; i) a[len - i - 1] s[i] - 0; } void print(int a[]) { int i; for (i LEN - 1; i 1; --i) if (a[i] ! 0) break; for (; i 0; --i) putchar(a[i] 0); putchar(\n); } void mul(int a[], int b[], int c[]) { clear(c); for (int i 0; i LEN - 1; i) { for (int j 0; j i; j) c[i] a[j] * b[i - j]; if (c[i] 10) { c[i 1] c[i] / 10; c[i] % 10; } } } int main() { read(a); read(b); sub(a, b, c); print(c); return 0; }高精度除法#include cstdio #include cstring constexpr int LEN 1004; int a[LEN], b[LEN], c[LEN]; void clear(int a[]) { for (int i 0; i LEN; i) a[i] 0; } void read(int a[]) { static char s[LEN 1]; scanf(%s, s); clear(a); int len strlen(s); for (int i 0; i len; i) a[len - i - 1] s[i] - 0; } void print(int a[]) { int i; for (i LEN - 1; i 1; --i) if (a[i] ! 0) break; for (; i 0; --i) putchar(a[i] 0); putchar(\n); } // 被除数 a 以下标 last_dg 为最低位是否可以再减去除数 b 而保持非负 // len 是除数 b 的长度避免反复计算 bool greater_eq(int a[], int b[], int last_dg, int len) { // 有可能被除数剩余的部分比除数长这个情况下最多多出 1 位故如此判断即可 if (a[last_dg len] ! 0) return true; // 从高位到低位逐位比较 for (int i len - 1; i 0; --i) { if (a[last_dg i] b[i]) return true; if (a[last_dg i] b[i]) return false; } // 相等的情形下也是可行的 return true; } void div(int a[], int b[], int c[], int d[]) { clear(c); clear(d); int la, lb; for (la LEN - 1; la 0; --la) if (a[la - 1] ! 0) break; for (lb LEN - 1; lb 0; --lb) if (b[lb - 1] ! 0) break; if (lb 0) { // 除数不能为零 puts( ); return; } // c 是商 // d 是被除数的剩余部分算法结束后自然成为余数 for (int i 0; i la; i) d[i] a[i]; for (int i la - lb; i 0; --i) { // 计算商的第 i 位 while (greater_eq(d, b, i, lb)) { // 若可以减则减 // 这一段是一个高精度减法 for (int j 0; j lb; j) { d[i j] - b[j]; if (d[i j] 0) { d[i j 1] - 1; d[i j] 10; } } // 使商的这一位增加 1 c[i] 1; // 返回循环开头重新检查 } } } int main() { read(a); read(b); sub(a, b, c); print(c); return 0; }压位乘法就是把原来一个数组元素存一位改为可自定义Karatsuba 乘法int *karatsuba_polymul(int n, int *a, int *b) { if (n 32) { // 规模较小时直接计算避免继续递归带来的效率损失 int *r new int[n * 2 1](); for (int i 0; i n; i) for (int j 0; j n; j) r[i j] a[i] * b[j]; return r; } int m n / 2 1; int *r new int[m * 4 1](); int *z0, *z1, *z2; z0 karatsuba_polymul(m - 1, a, b); z2 karatsuba_polymul(n - m, a m, b m); // 计算 z1 // 临时更改计算完毕后恢复 for (int i 0; i m n; i) a[i] a[i m]; for (int i 0; i m n; i) b[i] b[i m]; z1 karatsuba_polymul(m - 1, a, b); for (int i 0; i m n; i) a[i] - a[i m]; for (int i 0; i m n; i) b[i] - b[i m]; for (int i 0; i (m - 1) * 2; i) z1[i] - z0[i]; for (int i 0; i (n - m) * 2; i) z1[i] - z2[i]; // 由 z0、z1、z2 组合获得结果 for (int i 0; i (m - 1) * 2; i) r[i] z0[i]; for (int i 0; i (m - 1) * 2; i) r[i m] z1[i]; for (int i 0; i (n - m) * 2; i) r[i m * 2] z2[i]; delete[] z0; delete[] z1; delete[] z2; return r; } void karatsuba_mul(int a[], int b[], int c[]) { int *r karatsuba_polymul(LEN - 1, a, b); memcpy(c, r, sizeof(int) * LEN); for (int i 0; i LEN - 1; i) if (c[i] 10) { c[i 1] c[i] / 10; c[i] % 10; } delete[] r; }