题目描述

给定两个非负整数（不含前导 $0$） $A$，$B$，请你计算 $A/B$ 的商和余数。

输入格式

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

输出格式

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

数据范围

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

输入样例：

7
2

输出样例：

3
1

算法1

(高精度) $O(n)$

高精度除法要求求出商和余数，那我们的思路就是：把上一次的余数乘10，再加上当前位上的数，就是被除数，后面往C（答案）里压入这个数字除以$b$，就可以得到商在这个位置上的数字。

时间复杂度

参考文献

C++ 代码（无注释版本见高精度除法）

STL版本

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
vector <int> div(vector <int> &A,int b,int &r){ // 取r的地址符，是为了更改r的值，方便后面输出余数
    vector <int> C; // 答案
    r = 0; // 余数
    for(int i = A.size() - 1;i >= 0;i --){ // 从最高位开始处理
        r = r * 10 + A[i]; // 上一次的余数乘10，再加上当前位上的数，就是被除数
        C.push_back(r / b); // 往C里压入这个被除数除b
        r %= b; // 计算余数
    }
    reverse(C.begin(),C.end()); // 因为除法运算中从高位开始计算，而前导0都在顶部而不是底部，所以要翻转过来
    while (C.size() > 1 && C.back() == 0) C.pop_back(); // 去除前导0
    return C; // 返回答案
}
int main(){
    string a;
    int b;
    cin>>a>>b;
    vector <int> A;
    for(int i = a.size() - 1;i >= 0;i --) A.push_back(a[i] - '0'); // 倒序
    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;
}

数组版本

$$顺序输出，并且不需翻转c数组$$

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 100010;
string stra;
int lena,lenc;
int a[N],c[N],b;
int r; // 余数
int t = 1; // 前导0个数
void div(int a[],int b){
    for(int i = 1;i <= lena;i ++){ // 顺序计算
        r = r * 10 + a[i]; // 加上上一位留下的余数的十倍
        c[++ lenc] = r / b; // 将得到的数与b的商放入答案中
        r %= b; // 将余数模b，得到该位的余数
        // 如此循环，最终r就为a / b的余数了
    }
    while(c[t] == 0 && t < lenc) t ++; // 计算前导0数量，找到一个t ++
}
int main(){
    cin.tie(0);
    cin>>stra>>b; // 读入
    lena = stra.size();
    for(int i = 1;i <= lena;i ++) a[i] = stra[i - 1] - '0'; // 无需将a数倒序处理
    div(a,b); // 计算
    for(int i = t;i <= lenc;i ++) printf("%d",c[i]); // 从没有前导0的第一位开始输出
    printf("\n%d\n",r); // 输出余数
    return 0;
}

struct 数组模拟

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
using namespace std;
const int N = 1e5 + 10;
int r;
struct bignum{
    char s[N];
    int a[N],len;
    bool flag;
    bignum(){
        memset(a,0,sizeof a);
        len = 1;
        flag = 0;
    }
    bignum(int x){
        while(x){
            a[len] = x % 10;
            x /= 10;
            len ++;
        }
        len --;
    }
    int &operator [] (int i){
        return a[i];
    }
    friend bool operator < (bignum a,bignum b){
        if(a.len < b.len) return true;
        if(a.len > b.len) return false;
        for(int i = a.len;i >= 1;i --){
            if(a[i] < b[i]) return true;
            if(a[i] > b[i]) return false;
        }
        return false;
    }
    friend bool operator > (bignum a,bignum b){
        if(a.len < b.len) return false;
        if(a.len > b.len) return true;
        for(int i = a.len;i >= 1;i --){
            if(a[i] < b[i]) return false;
            if(a[i] > b[i]) return true;
        }
        return true;
    }
    friend bool operator == (bignum a,bignum b){
        if(a.len != b.len) return false;
        for(int i = a.len;i >= 1;i --){
            if(a[i] != b[i]) return false;
        }
        return true;
    }
    void input(){
        scanf("%s",s + 1);
        len = strlen(s + 1);
        for(int i = 1;i <= len;i ++) a[i] = s[len - i + 1] - '0';
    }
    void print(){
        if(flag) printf("-");
        for(int i = len;i >= 1;i --) printf("%d",a[i]);
    }
};
bignum operator / (bignum a,int b){
    bignum c;
    for(int i = a.len;i >= 1;i --){
        r = r * 10 + a[i];
        c[++ c.len] = r / b;
        r %= b;
    }
    reverse(c.a + 1, c.a + c.len + 1);
    while(c.len > 1 && c[c.len] == 0) c.len --;
    return c;
}
int main(){
    bignum a,c;
    int b;
    a.input();
    scanf("%d",&b);
    c = a / b;
    c.print();
    printf("\n%d\n",r);
    return 0;
}