【例1.5】高精除

题目描述

给定两个位数不超过 $299$ 的十进制正整数 $A$ 、 $B$ （各占一行，无前导零），求 $A = qB + r$ （ $0 \le r < B$ ）的商 $q$ 与余数 $r$ ，各占一行、不带前导零，商为 $0$ 时输出 0；样例输入 1231312318457577687897987642324567864324567876543245671425346756786867867867 与 1231312318767141738178325678412414124141425346756786867867867，对应输出 999999999748590 与 179780909068307566598992807564736854549985603543237528310337。

思路

用竖式长除法：从高位到低位依次把 $A$ 的一位拉下来，令当前余数 $r = 10r + d$ ，再反复减 $B$ 直到 $r < B$ ，减的次数就是这一位的商数字；商的位数至多 $n-m+1$ ，每位的试商是 $O(m)$ ，总复杂度 $O\big((n-m+1)m\big)$ 。注意商要去掉前导零（ $A < B$ 时商为 0），余数已保持无前导零的规范表示，直接输出即可。

参考代码

Python 版：

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-09-30 04:19
# update_at: 2026-09-30 04:37

import sys


def solve() -> None:
    """读入两个高精度正整数，输出它们的商和余数。"""
    # 两个操作数各占一行；split() 按空白切分，恰好得到两个 token
    a, b = map(int, sys.stdin.buffer.read().split())
    # int 是任意精度整数：竖式的逐位试商由解释器完成，同阶于手写长除法
    q, r = divmod(a, b)
    print(q, r, sep='\n')  # 商、余数各占一行


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-05 08:49
 * update_at: 2026-10-05 08:50
 */
#include <cstdio>
#include <cstring>
using namespace std;

typedef long long ll;

const int MAXLEN = 305; // 输入位数上限 300，开到 305 留余量

char str_a[MAXLEN];
char str_b[MAXLEN];
int a[MAXLEN];   // 被除数 A 的数位，a[0] 是最高位
int b[MAXLEN];   // 除数 B 的数位，b[0] 是最高位
int rem[MAXLEN]; // 当前部分被除数（余数），rem[0] 是最高位，无前导零
int q[MAXLEN];   // 商的数位，q[0] 是最高位
ll la;           // A 的位数
ll lb;           // B 的位数
ll lr;           // 当前余数的位数
ll lq = 0;       // 商的位数

// 把 rem 与 b 比较：rem > b 返回 1，相等返回 0，小于返回 -1。
int cmp_rem_b() {
    if (lr != lb) {
        return lr > lb ? 1 : -1;
    }
    for (ll i = 0; i < lr; i++) {
        if (rem[i] != b[i]) {
            return rem[i] > b[i] ? 1 : -1;
        }
    }
    return 0;
}

// 执行 rem = rem - b，要求调用前 rem >= b；b 的最低位对齐到 rem 的最低位。
void sub_b() {
    ll shift = lr - lb; // b[j] 对齐到 rem 的下标 j + shift
    ll borrow = 0;
    for (ll i = lr - 1; i >= 0; i--) {
        ll j = i - shift;
        ll sub = (j >= 0) ? b[j] : 0;
        ll t = rem[i] - sub - borrow;
        if (t < 0) {
            t += 10;
            borrow = 1;
        } else {
            borrow = 0;
        }
        rem[i] = t;
    }
    // 去掉最高位上的前导零，保持 rem 是规范表示。
    ll start = 0;
    while (start + 1 < lr && rem[start] == 0) {
        start++;
    }
    if (start > 0) {
        for (ll i = start; i < lr; i++) {
            rem[i - start] = rem[i];
        }
        lr -= start;
    }
}

int main() {
    if (scanf("%s", str_a) != 1) {
        return 0;
    }
    if (scanf("%s", str_b) != 1) {
        return 0;
    }
    la = strlen(str_a);
    lb = strlen(str_b);
    for (ll i = 0; i < la; i++) {
        a[i] = str_a[i] - '0';
    }
    for (ll i = 0; i < lb; i++) {
        b[i] = str_b[i] - '0';
    }

    lr = 1;
    rem[0] = 0; // 余数从 0 开始
    for (ll i = 0; i < la; i++) {
        // 竖式的一步：把 A 的下一位拉下来，rem = rem * 10 + a[i]
        rem[lr] = a[i];
        lr++;
        // 去掉新产生的前导零
        ll start = 0;
        while (start + 1 < lr && rem[start] == 0) {
            start++;
        }
        if (start > 0) {
            for (ll j = start; j < lr; j++) {
                rem[j - start] = rem[j];
            }
            lr -= start;
        }
        // 反复减 B，减的次数就是这一位的商数字
        ll digit = 0;
        while (cmp_rem_b() >= 0) {
            sub_b();
            digit++;
        }
        q[lq] = digit;
        lq++;
    }

    // 输出商，去掉前导零
    ll qs = 0;
    while (qs + 1 < lq && q[qs] == 0) {
        qs++;
    }
    for (ll i = qs; i < lq; i++) {
        printf("%d", q[i]);
    }
    printf("\n");
    // 输出余数（rem 已无前导零，至少有一位）
    for (ll i = 0; i < lr; i++) {
        printf("%d", rem[i]);
    }
    printf("\n");
    return 0;
}

目录

题目描述

思路

参考代码