笔记内容来源于算法基础课

大整数模拟

考虑$A, B$均为正整数，则模拟四种运算

$A + B, A - B | len(A) \sim len(B) \sim 10^6$
$A \times b, A \div b | len(A) \sim 10 ^6, b \sim 10^9$

存储

将每一位存储到字符数组，存储方向为下标从小到大 $\rightarrow$ 从低位到高位(当进位时能够方便地在数组末尾添加)

char[] a = sc.next().toCharArray(); // 数据太大，通过字符串读入，字符数组中为从高位到低位
List<Integer> A = new ArrayList<>();
for (int i = a.size() - 1; i >= 0; i--) A.add(a[i] - '0'); // 从地位到高位加入

而输出时注意从高位到低位输出

for (int i = C.size() - 1; i >= 0; i--) System.out.print(C.get(i));

大整数加法

遗留的进位为$t$, 在相加时遵循每位相加再加上进位，即$A_i + B_i + t$，当最高位包含不存在的数时$A_i or B_i = 0$, 当进位不存在时$t = 0$

// C = A + B
List<Integer> add(int[] A, int[] B) {
    List<Integer> C = new ArrayList<>();
    int t = 0; // 维护总和，初始进位为0
    for (int i = 0; i < A.length || i < B.length; i++) {
        if (i < A.length) t += A[i];
        if (i < B.length) t += B[i];
        C.add(t % 10);
        t /= 10; // 进位
    }
    if (t != 0) C.add(t); // 最高位存在进位
    return C;
}

大整数减法

$A \geq B$则直接相减，否则需要先输出-，再输出$B - A$

比较函数，从高位到低位，依次比较直至不同的位

boolean cmp(int[] A, int[] B) {
    if (A.length != B.length) return A.length > B.length; // 位数不同，则直接比较位数
    for (int i = A.length - 1; i >= 0; i--) { // 从高位到低位进行比较
        if (A[i] != B[i]) return A[i] > B[i];  // 如果两个位不相同，则直接比较大小即可
    }
    return true;
}

$C = A - B, A \geq B$

遗留的借位为$t$, 在相减时遵循每位相减再减去借位，即$A_i - B_i - t$，当其$\geq 0$则为该位的结果，当其$\le 0$则需要借位$+10$

综合考虑为$(A_i - B_i - t + 10) \bmod 10$

// C = A - B, A >= B
static List<Integer> sub(int[] A, int[] B) {
    List<Integer> C = new ArrayList<>();
    int t = 0; // 维护总和，初始借位为0
    for (int i = 0; i < A.length; i++) {
        t += A[i];
        if (i < B.length) t -= B[i]; // A[i] - B[i] - t
        C.add((t + 10) % 10);
        if (t < 0) t = -1; // 有借位
        else t = 0; // 无借位
    }
    while (C.size() > 1 && C.get(C.size() - 1) == 0) C.remove(C.size() - 1); // 去除前导0，但对于0来说不能删去唯一的0
    return C;
}

大整数乘法

遗留的进位为$t$, 在相乘时遵循每位为$(A_i \times b + t) \bmod 10$ 进位为$(A_i \times b + t) \div 10$

// C = A * B
List<Integer> mul(int[] A, int b) {
    List<Integer> C = new ArrayList<>();
    int t = 0; // 维护总和，初始进位为0
    for (int i = 0; i < A.length; i++) {
        C.add((A[i] * b + t) % 10);
        t = (A[i] * b + t) / 10;
    }
    while (t != 0) { C.add(t % 10); t /= 10; } // 最高位存在进位
    while (C.size() > 1 && C.get(C.size() - 1) == 0) C.remove(C.size() - 1);
    return C;
}

大整数除法

遗留的余数为$r$, 则在相除时商遵循从高到低计算，每位$(r \times 10 + A_i) \div b$ 余数为$(r \times 10 + A_i) \bmod b$

// C = A / B ... r
int r;
List<Integer> div(int[] A, int b) {
    List<Integer> C = new ArrayList<>();
    r = 0; // 维护总和，初始余数为0
    for (int i = A.length -  1; i >= 0; i--) {// 注意从高位向低位遍历
        C.add((r * 10 + A[i]) / b);
        r = (r * 10 + A[i]) % b;
    }
    Collections.reverse(C); // 得到的结果是从高位向低位添加的，因此注意反转
    while (C.size() > 1 && C.get(C.size() - 1) == 0) C.remove(C.size() - 1); // 开头存在无法上位的情况，因此存在前导0
    return C;
}

库函数

java提供了库函数可供调用

BigInteger(String val)
BigInteger add(BigInteger val)
int compareTo(BigInteger val)
BigInteger negate()
BigInteger multiply(BigInteger val)
BigInteger divide(BigInteger val)
BigInteger toString()