高精度除法

题目 高精度除法

image-a76a93dd

思路分析

image-d532ccea

与之前不同 这里从高位开始算

每位等于（前一位除以x的余数*10 +当前位）除以 x

留给下一位的就是这个 （前一位除以x的余数*10 +当前位）模上x

代码实现

#include<bits/stdc++.h>
using namespace std;
//除法的话正着存其实会更好算些 但是因为这种高精度的计算要出现的话往往是同时出现
//所以为了统一 对于除法也用这种逆序储存
//123/3
//1/3=0 余1
//1*10+2 /3 =12 余0
//0*3+3 /3 =1 余0
//结果为41 余0
//注意的是 与加减乘不同 除是从高位开始算的
//每轮的被除数都是前轮的余数*10+当前位的数
//结果就是/b
//余数就是%b
//捋清楚其实也是很简单的一个循环
//最后要注意的就是 因为刚开始是从高位开始算的 而结果是push_back进去的 所以最后要反转一下C
//别忘了取出前导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;
}

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--)
        printf("%d",C[i]);
    cout<<endl<<r<<endl;

    return 0;
}

同类题型

视频讲解

⬅️ 高精度乘法 🏠 00-听课板子 ➡️ 前缀和与差分