C++ / ACM 自学笔记 · v5.0

P1932 大整数五种运算

原题入口

对应章节:四、批量输入、大整数运算与提交检查 → (二) 大整数的加减乘除。

(一) 任务与输出目标

依次输出 A+B、A-B、A×B、A÷B 的整数商和余数。

(二) 建模与推导

每四位十进制数码组成一组,以 10000 为进制、低位在前保存。与逐位算法相比,20000 位变成约 5000 组;加法的进位、减法的借位、乘法的组位置相加完全沿用原来的推导。减法先比较绝对值,输出符号后做较大减较小。

除法仍按“旧余数乘进制、接下一组、确定商、减去商×除数”执行。为快速确定商,把两数同时乘 factor,使除数最高组不小于进制的一半。用余数最高两组除以除数最高组,得到不低于真实值、至多偏大两次的估计。每次发现乘积大于余数,就把估计减一、乘积减去一个除数。确认后写入商组,并把余数减去对应乘积。

共同放大不改变商,最后余数再除以 factor。每轮保持“已读前缀=商前缀×放大后的除数+余数”。因为估计来自最高部分,是真实商的上方候选,校正不会错过正确商。读入、比较、格式化分别放在类的方法里,五种运算共用同一存储表示。

(三) 手算与过程

A=987、B=23:和 1010、差 964、积 22701、商 42、余 21;42×23+21 恢复原数 987。

按具体数据展开的处理与返回过程

(四) 带注释实现

完整源文件

完整源文件按辅助状态与函数、solve() 中的单组计算、signed main() 中的公共调用顺序展开。先对照手算解释处理与返回过程,再打开源文件阅读、编译。

(五) 复杂度

n、m 为四位一组后的长度,加减 \(O(n+m)\),乘法 \(O(nm)\),长除法上界 \(O(nm+n+m)\),空间 \(O(n+m)\)。

返回本章题解索引 · 返回全部题号索引

查阅笔记正文与全部题解 · Ctrl / ⌘ K