进制转换问题

题目描述

编写一个程序，可以实现将一个数字由一个进制转换为另一个进制。

这里有 62 个不同数位：$\{0-9, A-Z, a-z\}$。

输入格式

第一行输入一个整数，代表接下来的行数。

接下来每一行都包含三个数字，首先是输入进制（十进制表示），然后是输出进制（十进制表示），最后是用输入进制表示的输入数字，数字之间用空格隔开。

输入进制和输出进制都在 2 到 62 的范围之内。

（在十进制下）$A=10，B=11，…，Z=35，a=36，b=37，…，z=61$ ($0-9$ 仍然表示 $0-9$)。

输出格式

对于每一组进制转换，程序的输出都由三行构成。

第一行包含两个数字，首先是输入进制（十进制表示），然后是用输入进制表示的输入数字。

第二行包含两个数字，首先是输出进制（十进制表示），然后是用输出进制表示的输入数字。

第三行为空白行。

同一行内数字用空格隔开。

输入输出样例

输入样例

8
62 2 abcdefghiz
10 16 1234567890123456789012345678901234567890
16 35 3A0C92075C0DBF3B8ACBC5F96CE3F0AD2
35 23 333YMHOUE8JPLT7OX6K9FYCQ8A
23 49 946B9AA02MI37E3D3MMJ4G7BL2F05
49 61 1VbDkSIMJL3JjRgAdlUfcaWj
61 5 dl9MDSWqwHjDnToKcsWE1S
5 10 42104444441001414401221302402201233340311104212022133030

输出样例

62 abcdefghiz
2 11011100000100010111110010010110011111001001100011010010001

10 1234567890123456789012345678901234567890
16 3A0C92075C0DBF3B8ACBC5F96CE3F0AD2

16 3A0C92075C0DBF3B8ACBC5F96CE3F0AD2
35 333YMHOUE8JPLT7OX6K9FYCQ8A

35 333YMHOUE8JPLT7OX6K9FYCQ8A
23 946B9AA02MI37E3D3MMJ4G7BL2F05

23 946B9AA02MI37E3D3MMJ4G7BL2F05
49 1VbDkSIMJL3JjRgAdlUfcaWj

49 1VbDkSIMJL3JjRgAdlUfcaWj
61 dl9MDSWqwHjDnToKcsWE1S

61 dl9MDSWqwHjDnToKcsWE1S
5 42104444441001414401221302402201233340311104212022133030

5 42104444441001414401221302402201233340311104212022133030
10 1234567890123456789012345678901234567890

字符与数值对应关系

算法步骤

1. 将输入的数字字符串从输入进制转换为十进制（大数）
2. 将十进制大数转换为输出进制
3. 按要求格式输出

需要注意的问题

1. 输入数字可能非常大，需要使用大数运算
2. 需要正确处理 0 的情况
3. 输出时要注意大小写字母的对应关系

大数运算思路

由于进制范围是 2 到 62，输入数字可能很长，无法用标准整数类型直接表示。需要实现：

1. 大数表示：使用字符串或数组表示大数
2. 进制转换算法：
   • 从输入进制到十进制：按位加权求和
   • 从十进制到输出进制：不断除以输出进制取余数

但由于数字可能非常大，直接从输入进制转到十进制可能产生极大的中间结果，更好的方法是：

• 先将输入进制数转换为十进制（使用大数运算）
• 再将十进制转换为输出进制

或者使用短除法直接进行任意进制转换：

1. 从输入进制转换为十进制
2. 从十进制转换为输出进制

因为输入可能非常大，需要使用大数除法。