题目描述

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

输入格式

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

输出格式

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

数据范围

$1≤A的长度≤100000$

$1≤B≤10000$

B 一定不为0

输入样例：

7
2

输出样例：

3

思路

和乘法差不多

模拟除法的竖式

每一次枚举的时候把上一次剩下的数乘以10，然后加上当前的数

然后把结果整除b，存下来，再把结果取余b，作为下一次的进位

最后要把整个动态数组进行翻转，然后再进行去前导0的工作（因为结果也是倒序存的，所以要先进行反转）

在调用函数的时候，引用了一个r，一定要引用，因为直接引用r，在函数里r会改变，在主函数里r也会随之改变

代码

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
vector<int> div(vector<int> &A,int b,int &r)
{
    r=0;
    vector<int> 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;
}
int main()
{
    vector <int> A;
    string a;
    int b;
    cin>>a>>b;
    for(int i=a.size()-1;i>=0;i--) A.push_back(a[i]-'0');
    int r;
    vector<int> C;
    C=div(A,b,r);
    for(int i=C.size()-1;i>=0;i--) cout<<C[i];
    cout<<endl<<r;
    return 0;
}

附：高精度除以低精度 —— 模板题 AcWing 794. 高精度除法

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