题目描述

原题

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

输入格式
共两行，第一行包含整数A，第二行包含整数B。

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

数据范围

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

输入样例：
7
2

输出样例：
3
1

算法

模拟手动除法的过程，注意每次过程中的余数是*10再加上大整数下一位的数，直到跟除数可以进行相除的时候。

参考文献

y总讲解视频

C++ 代码

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

using namespace std;

/*
a / b = c(商) ....r（余数）
*/
vector<int> div(vector<int> &a,int &b,int & r){
    vector<int> c;
    r = 0 ;
    //存储的时候是低位在前，但是除法是高位先除，所有从后面开始遍历
    for(int  i = a.size() - 1; i >= 0;i--){
        //当前余数都是上一位模掉余数的结果乘以10再加上当前位Ai
        r = r * 10 + a[i];
        //注意是余数除以除数，而不是除以10，放进答案数组里
        c.push_back(r / b);
        //模b得到下一次的余数
        r %= b;
    }
    //因为我们计算的时候是从高位开始计算，并且存储的时候 也是先存高位
    //但为了跟前面的高精度运算保持一致的存储顺序看，所以这里再反转一下
    //还是把低位放在前面，高位放在后面
    reverse(c.begin(),c.end());
    //这里处理的也是一种特殊情况，就是商的前面有多余的0的时候，把0去掉
    while(c.size() > 1 && c.back() == 0 ) c.pop_back();
    return c;
}

int main(){
    //用字符串存储大整数被除数
    string a;
    //小整数用int来存就行
    int b;
    vector<int> A;
    cin>>a>>b;
    for(int i = a.size() - 1; i >= 0 ; i--)A.push_back(a[i] - '0');
    //r是余数，不仅仅代表最后的余数，还是代表在每一次的除法运算过程中
    //的余数
    int r ;
    auto c = div(A,b,r);
    for(int i = c.size() - 1 ; i >= 0 ;i --)cout<<c[i];
    cout<<endl<<r<<endl;
    return 0;
}