题目描述

一个大整数a除以一个小整数b，输出其商与余数

样例

10000000000
9

算法1

除法模拟
大整数除小整数的除法

时间复杂度 O(n)

这里使用双端队列deque进行商的存储，可以避免将vector进行翻转再pop_back()的操作；

C++ 代码

#include<iostream>
#include<vector>
#include<deque>
using namespace std;

int div(const vector<int> &a, int b, deque<int> &c)  //a和c是引用传参，以避免拷贝，减少运行时间
{
    int t = 0;
    for(auto i : a){         //因为是从头遍历a，所以使用范围for循环；
        t = t * 10 + i;
        c.emplace_back(t/b);     //emplace_back()与push_back()操作相同但更优，可以作为替代
        t %= b;
    }
    while(c.front() == 0 && c.size() > 1)     //经典去除前导零，因为是deque所以避免了反转vector再pop_back();
        c.pop_front();
    return t;
}

int main()
{
    string n;
    int b; 
    cin>>n>>b;
    if(n == "0"){printf("0\n0"); return 0;}   //判一下n为0的情况
    vector<int> a;
    for(auto i : n) a.emplace_back(i-'0');     
    deque<int> c;
    int t = div(a, b, c);
    for(auto i : c) cout<<i;
    printf("\n%d", t);
    return 0;
}