#M072. 高精度进制转换

    ID: 5701 传统题 2000ms 512MiB 尝试: 2 已通过: 2 难度: 8 上传者: 标签>CF2500提高+/省选-进位制转换分治算法高精度乘法NTT中国剩余定理秦九韶算法难度分类

高精度进制转换

题目描述

这是一道模板题。

请实现一个程序,将一个非常大的非负整数由一个进制转换为另一个进制。

其中需要考虑的有 6262 个不同的数位 $\{\texttt{0}-\texttt{9},\texttt{A}-\texttt{Z},\texttt{a}-\texttt{z}\}$, 其中在十进制下,有 $\texttt{A}=10,\texttt{B}=11,\dots,\texttt{Z}=35,\texttt{a}=36,\texttt{b}=37,...,\texttt{z}=61$。

输入格式

第一行输入两个整数 a,ba, b ,表示输入数字的进制以及输出数字的进制。

第二行输入一个 aa 进制非负整数 XX。

输出格式

输出一个 bb 进制整数,为 XX 的 bb 进制表示。

36 10
1AZ
1691

数据范围与提示

对于 100%100\% 的数据,有:

2≤a,b≤622\le a,b\le 62。

1≤1\le XX 在 aa 进制表示下的长度 ≤105\le 10^5。

在 b≥4b\ge 4 时, 1≤1\le XX 在 bb 进制表示下的长度 ≤2×105\le 2\times 10^5。

在 b=3b=3 时, 1≤1\le XX 在 bb 进制表示下的长度 ≤3.5×105\le 3.5\times 10^5。

在 b=2b=2 时, 1≤1\le XX 在 bb 进制表示下的长度 ≤3×105\le 3\times 10^5。

所有评测数据随机生成。

为了方便各位进行本题调试对拍,本题提供采用 Go 语言实现的任意进制高精度非负整数转为 1010 进制输出的代码。请前往本题的附件区下载源代码文件。

上述代码采用了和本题完全一样的输入格式,但是在输出的时候忽略原有的输出进制,直接按照 1010 进制就行输出。 各位也可以用上述代码检查本题的 4040 组测试数据。

如果需要添加 Hack 数据(请保证与上述数据范围要求一致),欢迎添加讨论或者私信作者。