X进制减法算法解析与实现

1. X进制减法问题解析

这道题目来自蓝桥杯2022年第十三届省赛真题，考察的是X进制下的减法运算。题目要求我们计算两个X进制数的差，其中X进制指的是每一位的进制可能不同，但都大于等于2。

1.1 问题背景与理解

在常规的进制系统中，比如二进制、十进制，每一位的进制是固定的。而X进制则允许每一位有不同的进制。例如，一个3位数，从低位到高位可能是2进制、3进制、5进制。

题目给出两个数A和B，要求计算A-B的值。需要注意的是：

1. 两个数的位数可能不同
2. 每一位的进制取决于该位上A和B对应数字的最大值加1，且至少为2
3. 结果需要对1000000007取模

1.2 输入输出分析

输入格式：

• 第一行是一个整数n，表示最高位的进制（但实际可能不会用到）
• 第二行是ma，表示数A的位数
• 接下来ma个数字，表示A的每一位（从高位到低位输入，但程序中会反转存储）
• 然后是mb，表示数B的位数
• 最后mb个数字，表示B的每一位

输出格式：

• 一个整数，表示A-B的结果模1000000007

2. 算法设计与实现

2.1 数据结构选择

程序中使用了三个数组：

• a[]：存储数A的各位数字
• b[]：存储数B的各位数字
• sum[]：存储每一位的权重（即该位代表的实际值）

由于题目没有给出数字的最大位数，我们保守地选择了1000000的大小。

2.2 核心算法流程

1. 输入处理：

   • 读取n（虽然程序中没用到）
   • 读取ma和A的各位数字，注意是逆序存储（从a[ma-1]到a[0]）
   • 读取mb和B的各位数字，同样逆序存储

2. 计算每一位的进制：

   • 对于第i位，进制为max(a[i-1]+1, b[i-1]+1, 2)
   • 即取前一位两个数字的较大值加1，且至少为2
   • sum[i]表示第i位的权重，等于sum[i-1] * 进制

3. 计算A-B：

   • 从低位到高位，累加sum[i] * (a[i] - b[i])
   • 注意取模运算

2.3 关键代码解析

cpp复制sum[0] = 1;  // 最低位的权重是1
for(int i = 1; i < ma; i++) {
    sum[i] = sum[i