重刷五年前的题：进制转换里，一个字符造成的 WA

我准备把五年前刷过的题重新刷一遍，也把现在与当年的代码放在一起看。遇到难题就记录怎么突破；像这次这样，则留一篇短一点的错题记录。

这次是 洛谷 B3619：10 进制转 x 进制，题面给出 n ≤ 10^9、x ≤ 36，超过 9 的数码用大写字母表示。下文讨论非负整数与 2～36 进制。

现在的代码 WA 了两个点。翻出五年前的版本，代码短了很多，但我并没有特别理解它为什么成立。于是，这次要补的东西分成了两件：先找输出哪里错了，再把旧算法想明白。

先修错误：我要的是 A，输出的却是 65

#

现在的写法按位权拆数：先找不超过 n 的最大 x 的幂，再从高位到低位计算。例如 26 转二进制，就是依次处理 16、8、4、2、1。

这个思路可以成立，错误出在数码转换。原代码是：

1
2
3
4
5
6
7

ll trans(ll x)
{
    if (x < 10)
        return x;
    else
        return x - 10 + 'A';
}

输入 10 16，答案应该是 A，实际却输出 65。'A' 虽然写成字符，函数返回类型却是 ll，cout 最后按整数输出了它的编码值（这里是通常的 ASCII 环境）。

修复要同时改两处：返回类型改成 char，数字分支也返回字符。

1
2
3
4

char trans ( ll x ) {
    if ( x < 10 ) { return '0' + x ; }
    return 'A' + x - 10 ;
}

只改成 char，却保留 return x，会把 0～9 当成字符编码，依然不对。

还有一条要更正：最初讨论时提到了求幂溢出，但核对题目范围后，这并不是本题的原因。找到的第一个大于 n 的幂，最多为 36 × 10^9，远小于 long long 上限。不能把扩大范围后才有的风险，当成本次 WA 的解释。

目前能确定的是字符输出错误；没有两个失败测试点的具体数据，也就不能猜它们各自测了什么。

五年前的两行代码，到底做了什么？

#

旧代码的核心是：

1
2

ans += dict[n % x] ;
n /= x ;

先拿熟悉的十进制试一下：1234 % 10 = 4，1234 / 10 = 123。取余拿走末位，整除留下前面的部分。

换成 x 进制，也一样。假设四位数的数码是 a₃、a₂、a₁、a₀，展开后：

1
2

n = a₃×x³ + a₂×x² + a₁×x + a₀
  = x×(a₃×x² + a₂×x + a₁) + a₀

因为每位都小于 x，所以余数就是 a₀，商就是去掉末位后的数。整数除法与取余的关系，也可以对照 C++ 标准草案的乘除与取余规则：重点看 (a/b)*b + a%b = a。

以 26 转二进制为例：

余数依次是 01101。先取出的是最低位，所以反转得到 11010。

现在的代码从最高位拆，旧代码从最低位拆。旧写法省去了显式求幂，靠每轮整除把剩下的部分继续交给下一轮。

设结果有 d 位：现在的实现反复从头求幂，时间为 O(d^2)，直接输出，辅助空间为 O(1)；旧实现每轮拆一位，再反转字符串，时间为 O(d)，结果字符串占 O(d) 空间，除此之外只需 O(1)。本题最多 30 位二进制，性能差异很小，先把答案输出对才是关键。

它和辗转相除法很像，但下一步不同

#

我看到不断取余，第一反应就是辗转相除法。两者确实都用到了 a = q×b + r，不过：

• 进制转换保存余数，用商继续除以固定的进制。
• 辗转相除法用原除数和余数作为下一组数，寻找最大公约数。

后者依据 gcd(a, b) = gcd(b, a % b)。公约数能整除 a 和 b，也就能整除 a - q×b；反过来同样成立。两种算法共享除法关系，但循环中保留下来的东西不同。

旧代码也有遗漏：n = 0 时，while (n != 0) 一次也不执行，返回空串。我现在专门处理了零，这一点反而更完整。旧版倒序循环还用了无符号的 ans.length() - 1，空串时会先下溢；用 reverse 更省心。贴出的旧片段也缺少 ll 定义，独立编译需要补上。

留一份重新理解后的写法

#

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

#include<bits/stdc++.h>
using namespace std ;

using ll = long long ;

string ten_to_x ( ll n , ll x ) {
    const string dict = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ" ;
    string ans ;

    do {
        ans += dict[n % x] ;
        n /= x ;
    } while ( n != 0 ) ;

    reverse(ans.begin() , ans.end()) ;
    return ans ;
}

int main ( ) {
    ll n , x ;
    cin >> n >> x ;
    cout << ten_to_x(n , x) ;
    return 0 ;
}

while 先判断，do...while 先执行，因此后者至少执行一次。这里让零也记录一次 dict[0]，自然得到 "0"。想核对执行顺序，可以看 do 语句的条件检查位置，条件在每轮循环体之后检查。

顺手把 #define ll long long 换成了 using ll = long long ;：前者是预处理时的标识符替换，后者是遵守作用域的类型别名，两者没有运行速度差异。类型别名的定义也明确说明，别名不会创造新类型。

修正后的位权法与除基取余法，已在本地对 2～36 进制、零、一、幂附近、上界及随机输入作了对比检查；除基取余结果还做了转回十进制的核对。这里记录的是本地验证，没有把它写成一次新的洛谷 AC。

下次重刷前，遮住答案想一遍

#

• 数字 10、字符 'A'、整数编码 65，分别会怎样输出？
• 为什么 n % x 能拿到末位，为什么结果要反转？
• 输入是零时，循环究竟执行几次？

可复用的核心就是“记录 dict[n % x]，再令 n /= x”，直到数被拆完，最后反转。前三问的答案分别是类型决定输出方式、最低位先被取出、do...while 执行一次。

五年前已经写过这两行，现在还需要重新推导它。以后比较新旧代码时，我也想把这种空缺留下来：哪里写错了，哪里只是记得写法，哪里这次终于能自己解释。