题目描述

题目大意&链接

给定两个正整数，计算高精度整数除以低精度整数。

输入输出样例：
输入：

7
2

输出：

3
1

详情：ac_794高精度除法

解题思路

高精度除法需要注意3点。

除法和加减乘法不同，它可以正序存储，但为统一模板，这里也采用逆序将其存储，因此div函数的循环条件需要更改：
for(int i = A.size() - 1; i >= 0; i--)
{
...
}

余数 r 要模拟除法运算，r/b 作商的数值位；r %= b 作下一位的余数：

for(int i = A.size() - 1; i >= 0; i--)
{
    r = r * 10 + A[i];
    c.push_back(r / b);
    r %= b;
}

由于是逆序存储且逆序输出，则答案需要反转一下并去除结果的前导0：
reverse(c.begin(), c.end());
while(c.size() > 1 && c.back() == 0) c.pop_back();

完整代码

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

using namespace std;

vector<int> div(vector<int> &A, int b, int &r)
{
    vector<int> c;
    
    r = 0;  //余数先置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()
{
    string a;
    int b;
    vector<int> A;
    
    int r; //存储余数
    //高精度整数除以低精度整数
    cin>>a>>b;
    for(int i = a.size() - 1; i >= 0; i--) A.push_back(a[i] - '0');
    
    auto c = div(A, b, r);
    
    for(int i = c.size() - 1; i >= 0; i--) printf("%d", c[i]);
    printf("\n%d", r);
}

时间和空间复杂度

假设 a 和 b 的长度分别为 n 和 m，则：
时间复杂度：O(n + m)
空间复杂度：O(n + m)