企业官网建设流程全解析

最近整理 UVA 的旧题单，又翻到 13090 这道题。标题叫 Base of MJ，第一眼还以为是讲某个叫 MJ 的角色基地，结果题目拿到手里才发现，这就是一道典型的进制转换题。题解在网上不算多，不少新手卡在进制范围的判断和溢出处理上，所以决定把它拆开聊一聊。核心模型并不复杂：给一个由数字和大写字母组成的字符串，再给一个十进制目标值，找到一个最小的进制，使字符串按这个进制解读后等于目标值。这类问题在 UVA 里非常多，理解这一题之后，很多同类题都可以直接套用思路。

说实话，看到“Base”这个词，很多刚入门的朋友会下意识往“基地”方向想，甚至会脑补出什么地图题、模拟题。但刷多了就明白，UVa 的题目名字经常只是包装，比如用个人名、用个奇怪缩写，实际考的都是最朴素的数学点。Base of MJ 里的 MJ 是什么来头我至今没考证清楚，大概率就是题目里的一个角色名，算法上没有任何特殊含义。我们真正要处理的，是字符串、进制、十进制值三者之间的映射关系。

1. 先弄懂“Base of MJ”到底在问什么

1.1 去掉包装：MJ只是题目角色

题目原文我复述不全，但核心模型很标准。它给你一个字符串，比如101，再给一个数字 n，比如 5，问的是：存在哪个进制 base，使得101按 base 进制解读时，十进制值恰好等于 5？base 等于 2 的时候成立，因为 1*2^2 + 0*2^1 + 1*2^0 = 5。这题的“最小进制”往往就是答案，如果不存在，就输出题目要求的非法标记。

为什么强调最小进制？因为同一个字符串可能对应多个进制。比如10在二进制下是 2，在三进制下是 3，在十进制下是 10，几乎每个进制都对应一个不同值。但反过来，给定目标值 n 后，满足条件的进制可能不止一个，特别是只有一位字符的时候。A在 11 进制下值是 10，在 12 进制下值还是 10，在 100 进制下依然是 10。题目要是让你输出任意一个，那还好办，但通常要求最小的那个，所以必须二分到边界。

1.2 字符串里的A-Z不是字母，是数字

进制题里最常见的扩展字符集是 0-9 加上 A-Z。这 36 个符号分别代表数值 0 到 35。A 是 10，B 是 11，一直到 Z 是 35。为什么不用数字继续写？因为十进制符号只有 10 个，再往上就没得用了，只能借字母。很多刚接触的同学会在读入A之后直接当成字符处理，忘了转换成 10，这属于第一类常见 WA。

我习惯用一个统一的转换函数：

int charToVal(char c) { if ('0' <= c && c <= '9') return c - '0'; return c - 'A' + 10; }

这样无论处理数字还是字母，都走同一条路，不容易写乱。字符映射关系不复杂，但它会在后面的进制下界判断、单字符特判里反复出现，值得一开始就定清楚。

1.3 输入输出约定：怎么读、怎么判、怎么输出

按经典 UVA 惯例，这类题往往是多组数据读到 EOF，每组一行给一个字符串和一个 long long。字符串只有大写字母和数字，没有负号和小数点。输出通常带 Case 编号，例如Case 1: 7。有些题目找不到答案时输出 -1，有些会要求一个特定值，比如输出 0 或某个提示。老题目格式五花八门，我建议你动手前先把输出格式看清楚，别把精力耗在 WA 在格式这种不值当的地方。

如果你不确定原题的输出格式，最稳的法子是看 UVA 的 Sample Output。我的代码示例里用 -1 表示无解，实际提交时记得改成原题要求。

2. 核心原理：位权展开与字符映射

2.1 位权展开式与迭代式

进制转十进制，说穿了就是“每一位乘以对应的位权再相加”。比如2F在 16 进制下的值是 2*16^1 + 15*16^0 = 47。这里的 16^1、16^0 就是位权。用数学公式写出来很长，但编程时根本不用计算幂，迭代式更简洁：

value = 0 for each character c: value = value * base + digit(c)

举一个例子，字符串101在二进制下是怎么变成 5 的：先读入 1，value=1；再读入 0，value=1*2+0=2；再读入 1，value=2*2+1=5。每一步都相当于把之前的结果乘一次 base，再把当前数字放进来，和十进制里“拼数”的思路一模一样。这个迭代式是后面所有实现的核心，建议直接背下来。

2.2 字符转数字，三种写法的取舍

除了上面给出的 if-else 版本，字符转数字还可以写成查表或三元运算。查表最稳定，但需要编译器提前构建，适合一个程序里大量调用的情况。对于单道题，if-else 就够了。我更推荐把它拆成独立函数，而不是在主循环里写一堆判断，因为后面判断合法进制的下界时也要用同一个映射。

有人会直接用c - '0'去处理A，得到结果是负数，然后某一步进制判断出错。我在给新生 review 代码时见过太多次了。所以，尽早统一映射，后患少很多。你甚至可以写一个常量数组，把0-9A-Z映射到 0-35，每次查询直接查表，既快又不容易错。

2.3 合法进制的下界由最大字符决定

这一点是整个题的命门：进制 base 里不可能出现“等于 base 或大于 base”的数字符号。二进制的合法数字只有 0 和 1，所以字符串里如果出现2，这个串在二进制下就是非法表示。同理，一个包含A的字符串，进制至少是 11，因为 A 代表 10，而数字符号必须严格小于进制。

由此推出下界：

最小合法进制 = maxDigit + 1

同时进制不能小于 2，所以low = max(2, maxDigit + 1)。比如101最大数字是 1，下界是 2；2F最大字符是F（15），下界是 16。这段逻辑很薄，但它是后面二分范围的左端点，一旦算错，后面全白搭。计算 maxDigit 时直接用同一个字符映射函数，遍历一遍字符串即可。

3. 求进制范围：合法区间的数学推导

3.1 为什么不能蛮力枚举到天荒地老

拿到这道题，第一反应可能是从 low 开始往上枚举 base，一个一个试。枚举本身没错，但量级撑不住。假设目标 n 最大到 1e18，字符串是某个长串，可能在二进制下就已经超过 1e18，这时枚举 2 到 1e18 显然不可接受。

更严重的是：合法进制的上界并不是 36。虽然字符集只有 36 个符号，进制却可以远远超过 36。比如字符串A要想等于 10，进制取 11、12、13 都成立，上界是多少完全取决于目标 n。所以，我们必须用数学方式把搜索区间压缩，而不是默认枚举到 36 或 1e6 就结束。

3.2 单调性证明：进制增大，值不会变小

假设字符串从高位到低位是 d0, d1, ..., dm，在进制 b 下的值为：

V(b) = d0 * b^m + d1 * b^(m-1) + ... + dm

当 b 增大时，只要所有 digit 都小于 b，也就是 b 大于等于我们给定的下界，每一项 d_i * b^(m-i) 只会随 b 的增大而增大或不变，所以 V(b) 关于 b 是单调不减的。这是一条极其重要的性质：有了单调性，就能用二分搜索“第一个值不小于 target 的进制”，再去验证是否恰好相等。

这里要注意“不减”和“严格递增”的区别。只有一位的字符串，V(b) 恒等于那个 digit，不随 b 变化；全零字符串也一样。但“不减”已经够二分用了，因为我们要找的是“第一个 V(b) >= target”的位置。如果你把目标定成“找最小可行进制”，那么 lower_bound 天然能处理多解区间。

3.3 上界为什么取 target+1 就足够

很多人会问，二分上界设多少？设小了漏解，设大了怕溢出。我的答案很直接：取 target+1，再和下界取 max。

为什么够？分两种情况看。首先，当 target=0 时，上界自然就是 low，因为全零串在任何合法进制下都是 0，不需要往上找。其次，当 target>0 且字符串最高位不为 0 时，一旦 base 大于 target，V(base) 至少是 base 的若干倍，必然大于 target，所以答案只可能出现在 base <= target 的范围内。最高位是 0 的情况更特殊，此时 V(b) 的值其实由后续部分决定，增大 b 不会让它变大，如果当前区间的值已经到不了 target，再往上也到不了。因此把上界设在 target+1，既能覆盖所有可能解，又不会让搜索空间膨胀。

如果你嫌推导复杂，就记住：二分下界是 maxDigit+1，上界是 max(下界, target+1)。这个上界比很多人推荐的“枚举到 1e9”小得多，也严谨得多。

4. 完整实现：C++题解与逐段拆解

4.1 工具函数：字符转数值

先写一个独立的字符映射函数。它会反复被调用，所以尽量简洁、可读，不要在主函数里分散写。

int val(char c) { if ('0' <= c && c <= '9') return c - '0'; return c - 'A' + 10; }

这个函数必须覆盖所有输入情况。题目保证只有 0-9 和 A-Z，所以不需要处理小写字母。如果题目比较阴间地给了小写，可以加一个判断：先转成大写再转数值。不过 UVa 老题里一般不会这样刁难。

4.2 带溢出保护的计算函数

这个函数是整个解法的精华。很多人二分都写对了，唯独在 value 累加时溢出，导致 mid 处的比较结果异常。我用一个 limit 参数来限制值，只要超过 target 就提前返回 target+1，这样既保证比较逻辑正确，又不会溢出 long long。

判断溢出用了一个很常见的技巧：

if (v > (limit - d) / base) return limit + 1;

因为v * base + d可能溢出，所以改成先判断除法结果。在目标值不超过 1e18 的前提下，这个写法是安全的。如果你用的是更大范围的数据类型，也可以把 limit 换成4e18之类的值，但核心逻辑不变。

ll valueInBase(const string& s, ll base, ll limit) { ll v = 0; for (char c : s) { int d = val(c); if (d >= base) return limit + 1; if (v > (limit - d) / base) return limit + 1; v = v * base + d; } return v; }

这段代码里有两层保护。第一层判断当前 digit 是否小于 base，小于进制才合法；第二层判断乘法是否会溢出。两层都通过才更新 v。这样做的好处是，即使 base 非常大，函数也能在线性时间内给出正确比较结果。

4.3 二分查找与最小进制

二分部分是标准的 lower_bound。我们从 low 开始，直到 high，不断取 mid，调用 valueInBase 看是否达到 target。如果达到，说明 mid 可行或可能偏大，把右边界收缩到 mid；否则把左边界收缩到 mid+1。结束时 low 就是第一个可行进制。

ll solve(const string& s, ll target) { int maxDigit = 0; for (char c : s) maxDigit = max(maxDigit, val(c)); ll low = max(2LL, (ll)maxDigit + 1); ll high = max(low, target + 1); while (low < high) { ll mid = low + (high - low) / 2; if (valueInBase(s, mid, target) >= target) high = mid; else low = mid + 1; } return valueInBase(s, low, target) == target ? low : -1; }

注意mid = low + (high - low) / 2，而不是(low + high) / 2，后者在数值大时可能溢出。虽然这里 low 和 high 都不超过 1e18 量级，但养成这个习惯总是好的。二分结束后的验证也不能少，因为“第一个不小于 target 的进制”不一定恰好等于 target。

4.4 完整代码与复杂度分析

把上面的工具函数、计算函数、二分函数拼到一起，加上多组数据的输入输出，就得到完整解法。

#include <bits/stdc++.h> using namespace std; using ll = long long; int val(char c) { if ('0' <= c && c <= '9') return c - '0'; return c - 'A' + 10; } ll valueInBase(const string& s, ll base, ll limit) { ll v = 0; for (char c : s) { int d = val(c); if (d >= base) return limit + 1; if (v > (limit - d) / base) return limit + 1; v = v * base + d; } return v; } ll solve(const string& s, ll target) { int maxDigit = 0; for (char c : s) maxDigit = max(maxDigit, val(c)); ll low = max(2LL, (ll)maxDigit + 1); ll high = max(low, target + 1); while (low < high) { ll mid = low + (high - low) / 2; if (valueInBase(s, mid, target) >= target) high = mid; else low = mid + 1; } return valueInBase(s, low, target) == target ? low : -1; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); string s; ll n; int tc = 0; while (cin >> s >> n) { ll ans = solve(s, n); cout << "Case " << ++tc << ": " << ans << '\n'; } return 0; }

复杂度很容易算：valueInBase 内部是 O(L)，二分区间长度是 O(target)，但因为每次折半，所以总复杂度是 O(L * log(target))。如果 target 是 1e18，log 约 60，一个长度 1000 的字符串也只要几万次运算，完全够用。至于空间，除了存储字符串之外没有额外分配。

4.5 关于 lower_bound 的设计细节

我之所以强调用 lower_bound 而不是在二分里直接判等，是因为“等于 target”的进制可能不止一个。单字符字符串在很大一段进制范围内，值都不变，都等于同一个数。比如A在 11、12、13 等进制下都是 10。如果 target 是 10，我们想要的是 11，而不是 12、13。lower_bound 会先找到第一个不小于 10 的进制，正好是 11，再验证一下是否等于 10，完美。

如果你在普通二分里写死if (value == target) return mid; else ...，当存在多个解时，返回的 mid 可能是中间某个解，不一定最小。所以先 lower_bound，再验证，是最省心的做法。这也是很多老手推荐“二分答案后校验”的原因。

5. 实测踩过的坑：那些WA到怀疑人生的边界

5.1 单字符：“任何进制都可以”是最容易漏掉的

我第一版代码直接枚举进制然后验证相等，遇到 s=0, target=0 时输出了 2，题目如果觉得进制最小是 2，那么 2 就是标准答案。可是当 s=A, target=10 时，从 11 开始枚举，验证成立后输出 11，也没问题。问题出在二分判断里：如果返回的值恰好等于 target，但 mid 不是最小值，就会错。所以边界必须单独想清楚。

单字符情况有一个直观结论：若 s 的长度为 1，且 digit 等于 target，则最小进制是 max(2, digit+1)；否则无解。因为单字符在不同进制下的数值不会变，永远是那个 digit。这个结论可以在代码里做特判，但用 lower_bound 也能覆盖，只是你得确保二分上界不会把它排除。

5.2 溢出保护：一句除法判断救回整份代码

没有溢出保护的版本长这样：

v = v * base + d;

如果 base 很大，v 很快爆 long long，变成负数，然后二分逻辑彻底崩溃。比如 s=1000000000000000000000, target=1，进制从 2 开始，valueInBase 到第三步就已经超过 long long 了。所以必须在乘法前判断，公式是v > (limit - d) / base。limit 取 target 而不是 LLONG_MAX，能进一步避免无谓计算。这个技巧我在很多题解里见过，自己踩过一次之后才知道它有多重要。

还有一个容易忽略的细节：limit - d如果 d 非常大，比如 d 是 35，limit 是 10，那么limit - d变成负数，除法结果也是负数，比较会出问题。但由于我们在前面已经判断了d >= base，而 base 的最小合法值是 maxDigit+1，所以 d 一定小于等于 maxDigit，进制又至少是 maxDigit+1，所以当 base 合法时 d 不会大于 target？不一定，target 可能小于 d，比如 s=Z, target=10，那 d=35，target=10，base 至少是 36，在 valueInBase 中第一步判断 d >= base，35 >= 36 为假，进入溢出判断。此时(limit - d) / base=(10-35)/36是负数，v=0 不大于负数，然后v = 0*36+35 = 35，返回 35，接着二分会认为 35 >= 10，然后验等失败。逻辑没问题。所以只要先做d >= base判断，后面的负数情况就不会造成错误结果。如果你实在不放心，可以再加一句if (d > limit) return limit + 1;，一劳永逸。

5.3 前导零与全零串

前导零不影响进制合法性，但会影响单调性。s=012A在 high 足够大时，值主要由低位决定，但单调不减仍然成立，所以二分能用。全零串 s=00在任意进制下都是 0，如果 target=0，答案是下边界 low，即 2。如果 target>0，无解。很多同学会在全零串的二分里卡住，因为 value 永远是 0，永远小于 target，二分会把 low 一路推到 high，最后验证失败，这也算正常结果。

建议在代码里对全零串直接特判：如果所有 digit 都是 0，目标也是 0，输出最小进制；目标不是 0，输出无解。特判不算多余，它让逻辑更清晰。不过即使不特判，二分版本也能得到正确结果，只是多跑几次循环而已。

5.4 对拍：暴力枚举就是最可靠的裁判

写完二分，我强烈建议你写一个暴力函数，从 low 开始一直枚举到 1e6 或更远，检查能否找到目标进制。把它和二分答案对拍几千组随机数据。随机数据怎么造？就是随机生成一个由 0-9、A-Z 组成的字符串，随机生成一个 target，然后两个函数输出做比较。

我实际对拍时抓到过一个隐藏问题：字符串长度超过 1000，二分时溢出保护正常，但暴力枚举到很远的进制后，valueInBase 因为 d >= base 直接返回 limit+1，导致比较失真。后来在暴力里也加上同样的判断，才真正对齐。对拍代码不用很复杂，甚至可以直接在本地写一个 50 行的 checker，比人眼查边界可靠得多，尤其是这种数据范围大、边界多的题。

6. 从这一题总结进制问题的通用套路

6.1 进制题最常见的四种变体

我刷了几百道题后发现，进制题的变体基本绕不开四种。第一种就是 UVa 13090 这种：给字符串和十进制目标，求最小进制。第二种是给一个十进制数，反向求它在某个进制下的表示。第三种是给你一个等式，比如ABC + DEF = GHI，求能使等式成立的进制。第四种是判断一个字符串在哪些进制下是回文数、素数或满足某个数论性质。

无论哪一种，第一步都是先确定字符到数值的映射，第二步确定合法进制的下界，第三步再考虑用枚举还是二分。把这三步走稳，变体再多也万变不离其宗。等式类的问题还要小心运算结果溢出，通常会把两边的值同时算到一个 long long 里，或者用高精度。

6.2 选枚举还是选二分，边界在哪里

如果进制范围压得很小，比如题目保证 base 在 2 到 36 之间，那么直接枚举最省事，代码也更好读。但如果没有这个保证，目标值又很大，就一定要二分。判断依据只有一个：合法进制的可能范围有多大。范围小用枚举，范围大用二分。二分时需要保证 value 关于 base 单调不减，而进制题里这个性质几乎天然成立，因为每一位数字符号都小于进制，所以大进制下每一位的位权都不会变小。

如果题目涉及等式两边，比如 A+B=C，你还可以先推导出进制的一个二次或一次函数，用数学方式直接解出来，速度更快。比如形如AB + CD = EF的式子展开后，会得到一个关于 base 的线性方程，解出来再验证是否满足每一位 digit 小于 base 即可。

6.3 我的个人习惯

最后说点我自己的做题习惯。拿到任何进制题，我第一件事不是写代码，而是先算下界和上界。下界由最大字符决定，上界要么由题目限定，要么用 target 相关值，这两个端点写注释标出来，后面调试会省很多时间。其次是保证字符转数字函数只有一个版本，不要在多个地方重复写判断，否则改一处忘一处，迟早炸。最后，每次交题前务必对拍一次，特别是涉及 long long 和二分的问题，极端数据远比你想象的多。

如果你刚接触 UVa 13090，建议先把暴力版本写出来跑一遍样例，再用二分版本替换，这样能直观感受到单调性质和边界条件的差别。只要把上面这些点吃透，同类的进制题基本不会再让你头疼。我在实际刷题过程中最大的体会是：进制题很少考高深算法，考的就是基础功和细心，尤其手动枚举几个样例之后，很多隐藏问题会自己浮出来。