N. HugeInteger 大整数运算 (Easy)

传统 1000 ms 256 MiB
标准 IO
文本比较

题目描述

请创建一个名为 HugeInteger 的类,用于处理超大整数的存储与运算。

虽然基础要求是用一个固定大小的数组来存放,但为了应对本题的 加强版数据,你需要对内部存储结构进行优化(例如使用动态数组或压位存储)。

你需要实现以下功能:

  1. 数值存储:能够处理长度达到 3×1043 \times 10^4 位的非负整数。
  2. 运算支持
    • ADD:加法。
    • SUB:减法(保证被减数大于等于减数)。
    • MUL:乘法(本题核心难点,需高效实现)。
  3. 比较支持
    • EQUAL:判断是否相等。
    • GREATER:判断是否大于。
    • LESS:判断是否小于。

输入说明: 每组数据包含一个操作指令字符串,以及两个大整数 AABB。你需要根据指令计算结果或输出布尔判断。

输入格式

第一行包含一个整数 1T501 \le T\le 50,表示测试数据的组数。

接下来 TT 行,每行格式如下:

OperationABOperation \quad A \quad B

其中 OperationOperation 为字符串指令,取值为 ADD, SUB, MUL, EQUAL, GREATER, LESS 之一。

AABB 为两个非负大整数的字符串形式。

输出格式

对于每组数据,输出一行:

  • 若是运算指令(ADD, SUB, MUL),输出计算结果的十进制字符串。
  • 若是比较指令(EQUAL, GREATER, LESS),若条件成立输出 True,否则输出 False

样例

样例输入

4
ADD 123456789 987654321
SUB 1000 1
MUL 99999 99999
GREATER 500 100

样例输出

1111111110
999
9999800001
True

数据范围与提示

  • 数据共分为两档:
    • Small (30%):数字长度 L1000L \le 1000。普通的一位一存模拟即可通过。
    • Large (70%):数字长度 L30000L \le 30000
  • 提示
    • 对于 3000030000 位的乘法,如果使用简单的 O(N2)O(N^2) 且不进行压位(一位一存),运算次数约为 9×1089 \times 10^8,可能会超时。
    • 建议实现 压位(High-Radix) 技术,例如每 8 位或 9 位存为一个 int,将计算复杂度降低约 64648181 倍。
    • 减法保证结果非负。