AcWing 794. 高精度除法

[toc]

第一讲 基础算法 - 04高精度 | Akari的小站

---

AcWing 794. 高精度除法【简单】

1 题目描述

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

输入格式:
共两行，第一行包含整数 A，第二行包含整数 B。

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

数据范围:
1 ≤ A 的长度 ≤ 100000,
1 ≤ B ≤ 10000,
B 一定不为 0

输入样例:

7
2

输出样例：

3
1

2 算法步骤

大整数 ÷ 小整数.

1. 高精度数组利用字符串读入
2. 把字符串翻转存入两个整型数组 A, B
3. 从高位到低位, 当前被除数, 存商, 求余数 *
4. 把数组 C 从高位到低位依次输出

3 时间复杂度

时间复杂度: O(n)

4 AC代码

4.1 数组

注意 : lc = la, 结合图片去理解.

#include <bits/stdc++.h>
#define endl '\n'
using namespace std;

typedef long long LL;
LL r;       // 计算当前被除数，或者说余数
const int N = 1e5 + 10;
int A[N], b, C[N];
int la, lc;

void div(int A[], int b, int C[]);

int main(void)
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    string a;
    cin >> a >> b;
    lc = la = a.size();     // lc = la
    for (int i = la - 1; ~i; i -- ) A[la - 1 - i] = a[i] - '0';     // 翻转存入
    div(A, b, C);
    for (int i = lc; ~i; i -- ) cout << C[i];       // 逆序输出
    cout << endl << r << endl;
    
    return 0;
}

void div(int A[], int b, int C[]){
    r = 0;
    for (int i = la - 1; ~i; i -- ){
        r = r * 10 + A[i];          // 被除数
        C[la - 1 - i] = r / b;      // 存商
        r %= b;                     // 余数
    }
    reverse(C, C + lc);
    while (lc && C[lc] == 0) lc -- ;    // 处理多余0
}

4.2 vector

#include <bits/stdc++.h>
#define endl '\n'
using namespace std;

typedef long long LL;
typedef vector<int> VI;
LL r;       // 计算当前被除数，或者说余数
VI A, C; int b;

void div(VI &A, int b, VI &C);

int main(void)
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    string a;
    cin >> a >> b;
    for (int i = a.size() - 1; ~i; i -- ) A.push_back(a[i] - '0');      // 翻转存入
    div(A, b, C);
    for (int i = C.size() - 1; ~i; i -- ) cout << C[i];     // 逆序输出
    cout << endl << r << endl;
    
    return 0;
}

void div(VI &A, int b, VI &C){
    r = 0;
    for (int i = A.size() - 1; ~i; i -- ){
        r = r * 10 + A[i];      // 被除数
        C.push_back(r / b);     // 存商
        r %= b;                 // 余数
    }
    reverse(C.begin(), C.end());
    while (C.size() > 1 && !C.back()) C.pop_back();     // 处理多余0
}