A4 高精度除法 • EH's Blog

题目情境#

题目链接：https://www.luogu.com.cn/problem/P1480 ↗

题目描述

输入两个整数 a,b，输出它们的商。

输入格式

两行，第一行是被除数a，第二行是除数b。

0 ≤ a ≤ $10^{5000}$ ，1 ≤b≤ $10^{9}$

输出格式

一行，商的整数部分。

输入输出样例

输入 #1

2
1

plaintext

输出 #1

plaintext

算法解析#

高精度/低精度步骤：

高精度数以字符串读入
翻转存入整型数组A
高位到低位逐位计算，存商求余
高位到低位输出数组C 此算法的除数要求不能是高精度的时间复杂度O( $n$ )

Python代码实现#

a = int(input())
b = int(input())
print(a // b)

python

C++代码实现#

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

const int N=5005;
int a[N],b,c[N];
int len;

void div(int a[],int b,int c[]){ //a/b=c
    long long t=0;
    for(int i=len;i>=1;i--){
        t=t*10+a[i];  //被除数
        c[i]=t/b;     //存商
        t%=b;         //余数
    }
    while(c[len]==0&&len>1) len--; //去0
}
int main(){
    char A[N]; cin>>A>>b; len=strlen(A);
    for(int i=1;i<=len;i++) a[i]=A[len-i]-'0';
    div(a,b,c);
    for(int i=len;i;i--) cout<<c[i];
    return 0;
}