高精度除法

一、算法思想

使用数组来存储大整数，需要说明的是，如果题目中只有除法运算，那么按照由高位到低位存储会更方便。但为了与其他运算统一处理，这里仍然选择由低位到高位的顺序存储。

注意

该模板仅考虑高精度除以低精度的情况。

二、算法模板

C++

// 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());
    
    // 去除前导 0
    while (C.size() > 1 && C.back() == 0) C.pop_back();
    
    return C;
}

Go

func div(A []int, b int) (C []int, r int) {
    for i := len(A) - 1; i >= 0; i-- {
        r = r*10 + A[i]
        C = append(C, r/b)
        r %= b
    }
    // reverse
    for i, j := 0, len(C)-1; i < j; i, j = i+1, j-1 {
        C[i], C[j] = C[j], C[i]
    }
    // 去除前导 0
    for len(C) > 1 && C[len(C)-1] == 0 {
        C = C[:len(C)-1]
    }
    return
}

三、代码实战

AcWing 0794

---

题目：高精度除法

给定两个非负整数（不含前导 $0$）$A$ 和 $B$，请你计算 $A \div B$ 的商和余数。

输入格式

共两行，第一行包含整数 $A$，第二行包含整数 $B$。

输出格式

共两行，第一行输出所求的商，第二行输出所求余数。

数据范围

$1\le \text{A 的长度} \le 10^5$

$1\le \text{B} \le 10^4$

输入样例：

7

2

输出样例：

3

1

解答代码：

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

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());
    
    // 去除前导 0
    while (C.size() > 1 && C.back() == 0) C.pop_back();
    
    return C;
}

int main()
{
    string a;
    int b;
    vector<int> A;
    
    cin >> a >> b;
    for (int i = a.length() - 1; i >= 0; i--) A.push_back(a[i] - '0');
    
    int r;
    vector<int> C = div(A, b, r);
    for (int i = C.size() - 1; i >= 0; i--) printf("%d", C[i]);
    cout << endl << r << endl;
    
    return 0;
}

package main

import (
    "bufio"
    . "fmt"
    "io"
    "os"
)

// 高精度除法
// A / b = C ... r，满足 A >= 0, b > 0
func div(A []int, b int) (C []int, r int) {
    for i := len(A) - 1; i >= 0; i-- {
        r = r*10 + A[i]
        C = append(C, r/b)
        r %= b
    }
    // reverse
    for i, j := 0, len(C)-1; i < j; i, j = i+1, j-1 {
        C[i], C[j] = C[j], C[i]
    }
    // 去除前导 0
    for len(C) > 1 && C[len(C)-1] == 0 {
        C = C[:len(C)-1]
    }
    return
}

func run(_r io.Reader, out io.Writer) {
    in := bufio.NewReader(_r)

    var a string
    var b int
    Fscan(in, &a, &b)

    var A []int
    for i := len(a) - 1; i >= 0; i-- {
        A = append(A, int(a[i]-'0'))
    }
    C, r := div(A, b)
    for i := len(C) - 1; i >= 0; i-- {
        Fprintf(out, "%d", C[i])
    }
    Fprintf(out, "\n%d", r)
}

func main() {
    run(os.Stdin, os.Stdout)
}