SolitudeAlma

今天我们来介绍一下高精度除法

什么是高精度除法呢？

我们来看看百度百科是怎么介绍高精度除法的，但是并没有搜到相关信息，逛了一圈发现也没人介绍，那我在这里就简单提一下。

一般我们计算高精度除法分为高精度除高精度和高精度除低精度，在这里我们只讲第二种，计算的过程很多时候都是不能整除的，所以我们需要计算商与余数，计算过程也非常简单。

首先我们回想一下在草稿纸上我们是如何计算的，第一步看最高位，最高位除以除数作为商的第一位，对除数求余作为下一步计算的数的一部分，每一次求余过后我们都让余数扩大10倍再加上下一位，如此往复计算即可。

那么我们来看看模板是怎么写的

vector<int> div(vector<int> &A , int b , int &r)
{
    vector<int> C;
    r = 0; //余数，这里用到了C++的引用，所以返回的时候可以不用返回余数
    // 这里正着算，从最高位开始
    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()); //这里将数组翻转过来，因为我们需要去掉前导零
    while(C.size() > 1 && C.back() == 0) C.pop_back();
    return C;
}

接下来试试模板题吧

AcWing 794.高精度除法

题目描述

给定两个非负整数A，B，请你计算 A / B的商和余数。

输入格式

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

输出格式

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

数据范围

$1≤A的长度≤100000,$
$1≤B≤10000$
$B 一定不为0$

输入样例：

7
2

输出样例：

3
1

C++代码

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

using namespace std;

vector<int> A;
string a;
int b;

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());

    while(C.size() > 1 && C.back() == 0) C.pop_back();

    return C;
}

int main()
{
    cin >> a >> b;

    // 因为高精度计算往往并不是单单一个，而是两三个一起，所以我们在这里统一存入方式，避免不必要的错误
    for(int i = a.size() - 1; i >= 0; i--) A.push_back(a[i] - '0');

    int r;
    auto C = div(A , b, r);

    for(int i = C.size() - 1; i >= 0; i --) cout << C[i];
    cout << endl << r;

    return 0;
}

引用

引用一些比较好的题解，比较详细有配图

空_22 AcWing 794. 基础_高精度_高精度除法java_python_c++

zyz. AcWing 794. 高精度除法

Bug_FreeOωO AcWing 794. 高精度除法

高精度除法的介绍以及模板的分享