题目描述

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

样例

7
2

3
1

算法

(枚举)

1. 除法的话，要多输出1个余数，所以我们的函数是div(A, b, t)，其中t表示余数
2. div()函数中的for()循环那里背过就好了。
3. 因为除法必须从高位开始处理，所以这里是从A.size() - 1开始枚举的。
4. 因为会有前导零的存在，我们用vector存的，只能处理back()，所以reverse()一下，刚好也能对应上之前3个同类型题的输出。

时间复杂度

$O(n)$

C++ 代码

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

using namespace std;

vector<int> div(vector<int> &A, int &b, int &t)
{
    t = 0;
    vector<int> C;
    // for(int i = C.size() - 1; i >= 0; i --) // **2
    for(int i = A.size() - 1; i >= 0; i --)
    {
        t = t * 10 + A[i];                   // **1
        C.push_back(t / b);
        t = t % b;
    }

    reverse(C.begin(), C.end());             // **3

    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.size() - 1; i >= 0; i --) A.push_back(a[i] - '0');

    int t;                                                      // **4
    auto C = div(A, b, t);

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

    return 0;
}