1. 项目缘起从一道“甲级”真题说起最近在刷算法题偶然翻到一道PATProgramming Ability Test甲级的真题编号是1010标题叫“Radix”。这道题在各大算法社区和备考群里的“名声”相当响亮属于那种一看题干觉得平平无奇上手一写就漏洞百出最后能把人折磨得欲仙欲死的经典“坑题”。我自己的第一遍提交毫不意外地吃了个“Wrong Answer”后来静下心来结合网上一些零散的讨论比如用户xp_xht123可能分享过的思路才算是把里面的弯弯绕绕彻底理清。这道题的核心是“进制转换”与“二分查找”的结合但它绝不仅仅是这两个知识点的简单拼接。题目会给你两个数N1和N2以及其中一个数的进制tag和radix让你求另一个数在何种进制下能与已知进制的数相等。听起来很简单对吧但魔鬼全藏在细节里未知进制的下限怎么定上限又在哪里数值溢出怎么办搜索范围巨大时如何高效求解每一个问题处理不好都会导致答案错误。所以这篇内容不是一份简单的题解而是一次完整的“踩坑复盘”和“思维重塑”。我会带你从最朴素的暴力解法开始一步步分析为什么它会失效然后引出正确的“二分溢出判断”框架并深入探讨那些教科书和普通题解里不会告诉你的边界条件与实战技巧。无论你是正在备战PAT、PTA还是单纯想提升自己解决复杂模拟题的能力相信这些从实际调试中获得的经验都比单纯的AC代码更有价值。2. 题目重述与核心难点拆解我们先来准确理解一下题目“1010 Radix”到底在问什么。题目的大意如下给定两个数 N1 和 N2以字符串形式给出并给定其中一个数所属的进制 tag1或2和 radix进制值2到36之间。要求找出另一个数在何种进制下其值能与已知进制的那个数相等。如果存在多个这样的进制输出最小的一个如果不存在则输出“Impossible”。例如输入可能是6 110 1 10。这表示N1”6” N2”110”且tag1即N1的进制是已知的radix10即N1是十进制。那么我们需要求N2”110”在多少进制下其值等于十进制的6。显然110在二进制下就是6所以输出2。核心难点一进制的下限与上限这是第一个拦路虎。未知进制的下限low不能想当然地设为2。正确的下限应该是max(2, max_digit 1)。其中max_digit是未知数字符串中最大数字字符所对应的数值0-35a-z代表10-35。因为进制数必须大于任何一位上的数字比如数字”1a”它的进制至少是11因为a代表10。难点在于上限high。一个最直观的错误想法是上限就是已知数的值设为target_val或者36。但考虑这个例子已知十进制数N1”100”求N2”1”的进制。要使”1”在某个进制下等于100这个进制只能是100吗不对”1”在任何进制下的值都是1。所以当N2只有一位时它只有在值等于target_val时才有解且进制可以是target_val1以上的任意值但题目要求输出最小的所以此时进制应该是target_val1不这里又有一个坑如果target_val小于等于max_digit那根本无解如果大于则最小进制是target_val1吗我们稍后详细分析。更常见的情况是N2有多位那么它的值随着进制增长会变得非常快上限需要谨慎设定。核心难点二数值溢出与比较策略进制可能很大比如未知数是”zzzzzzzzzz”在寻找其进制时计算它的十进制值很容易超过任何基本数据类型如long long的表示范围导致溢出得到错误的结果。因此不能在二分过程中直接计算未知数的完整十进制值来与目标值比较。我们必须设计一种不会溢出的比较方法。核心难点三二分查找的单调性与终止条件假设我们正确设定了上下界并且有了安全的比较函数接下来就是二分查找。这里的关键是证明“未知数的值随进制增大而严格单调递增”。对于长度大于1的数字字符串这一点是成立的。但对于长度为1的字符串呢例如数字”5”它在任何进制下的值都是5是常数不满足单调性。这是一个特例需要单独处理。二分查找的终止条件、以及如何从可能的多个解中找到最小的那个也需要仔细设计。3. 从暴力搜索到二分优化思路的演进我们先来看看最直接的暴力搜索思路以及它为什么行不通。3.1 朴素的暴力解法暴力法的逻辑很直接将已知进制的数转换为十进制值记为target。从下限low开始逐个尝试进制radix直到一个预设的上限high比如设为target1或 36。对于每个尝试的进制将未知数转换为十进制值current。比较current和target如果current target找到解输出当前进制。如果current target由于值随进制增大而增大后续的进制只会使current更大所以可以提前结束输出“Impossible”。如果遍历完所有进制都没找到输出“Impossible”。这个算法在遇到像N1”1”, N2”1”这样的数据时上限设为target1会错过解因为”1”在任意大于1的进制下都是1。但更致命的问题是效率。考虑这个极端案例N1”1000000000” (十进制) N2”1000000000”。未知数的下限是11因为最大数字是’0’所以是max(2, 01)2但实际最小是2这里注意数字都是0-9所以下限是2。但它的值要增长到10亿。进制从2开始尝试每次计算一个10位数的进制转换这计算量是天文数字必然超时。3.2 引入二分查找既然未知数的值f(radix)在进制radix上是单调递增的对于长度1的情况那么在一个有序区间[low, high]内查找满足f(radix) target的radix二分查找是标准操作能将时间复杂度从 O(N) 降为 O(log N)。但这就引出了前面提到的两个核心问题上下界如何确定low已知high应该设多大如何比较f(radix)和target而不溢出对于问题1一个可靠的上界设定是high max(low, target) 1。为什么是target 1考虑未知数N2”10”target100。当进制是100时”10”表示1*100^1 0*100^0 100刚好等于target。当进制大于100时值会大于100。所以解可能出现在target附近。但为什么还要1并和low取max这是为了处理边界确保二分区间[low, high]是有效的并且能覆盖到radix target这个点如果它是解。实际上更严谨的上界可以设为max(low, target) 1但还有一种更紧的界我们后面讲。对于问题2我们不能计算完整的f(radix)但可以在计算过程中进行“提前比较”。具体来说我们从高位到低位计算f(radix)的部分和sum。在计算的每一步我们都检查如果当前的sum已经大于target那么即使后面的低位全为0最终结果也肯定大于target可以立即返回1表示current target。如果计算完所有位sum小于target则返回-1等于则返回0。这种方法完全避免了溢出。4. 实战代码框架与关键函数实现理解了思路我们来看具体的代码实现。我会用C作为示例语言因为PAT环境主要支持C/C。4.1 辅助函数字符到数值的转换long long charToVal(char c) { if (c 0 c 9) return c - 0; else return c - a 10; // 题目说明字母为小写 }4.2 核心函数安全比较cmp这个函数是算法的灵魂它判断在给定进制radix下未知数字符串str对应的值是否等于、大于或小于目标值target。// 返回值-1 (值 target), 0 (值 target), 1 (值 target) int cmp(const string str, long long radix, long long target) { long long sum 0; for (char c : str) { sum sum * radix charToVal(c); // 关键防止溢出和提前判断 if (sum 0 || sum target) { return 1; // 溢出或已大于目标值 } } if (sum target) return -1; if (sum target) return 0; return 1; // 理论上不会走到这里 }注意if (sum 0)这一句这是检测溢出的经典方法。当sum * radix的结果超过long long最大值时会发生溢出sum可能变成一个负数。因此一旦sum变负我们可以断定实际值已经巨大无比肯定大于target。4.3 主逻辑与二分查找统一处理将已知进制的数转换为target。确定未知数的进制下界low。单独处理长度为1的特例如果未知数长度为1那么它的值是一个常数val。只有当target val时才有解且最小的进制是max(low, val 1)等等这里需要仔细推敲如果target val那么val在任意大于等于low且大于val的进制下都成立吗不对”1”在任何进制下都是1。所以条件是target必须等于val。此时最小的进制应该是max(low, 2)吗不应该是low吗我们举个例子target5,str”5”,lowmax(2, 51)6。那么进制6是解吗是的”5”在6进制下就是5。但进制5呢5进制下数字’5’是非法的因为最大数字是4。所以对于一位数的情况解必须满足两个条件a)target val b) 进制radix val因为该数字字符在radix进制下必须合法。所以最小进制是max(low, val 1)。如果low val 1则解就是low如果low val1则解是val1。但low本身已经保证了radix val因为low max(2, max_digit1)而一位数时max_digit val所以low一定大于val。因此对于一位数只要target val答案就是low。对于长度大于1的情况进行二分查找。上界high的设定是个关键。一个足够大且安全的上界是max(low, target) 1。但更精确的做法是考虑到target可能非常小而low可能很大例如未知数是”abcdef”low至少是16此时上界应该至少是low。所以上界可以设为max(low, target) 1。但还有一种情况target可能小于low此时上界设为low1即可因为进制小于low是非法的。实际上我们可以将上界初始化为max(low, target) 1然后在二分过程中动态调整或者直接设一个非常大的值如1LL 60但二分次数是 log(范围)范围太大虽然不会错但可能因为cmp函数中溢出判断的逻辑导致在极大进制下sum第一次乘就溢出返回1从而让二分快速收敛。二分查找的循环long long low ...; // 计算得到 long long high max(low, target) 1; // 初始上界 long long ans -1; while (low high) { long long mid low (high - low) / 2; int result cmp(unknown_str, mid, target); if (result 0) { ans mid; // 寻找最小的进制所以继续在左半边查找 high mid - 1; } else if (result 1) { // 当前值大于目标值或溢出进制太大了 high mid - 1; } else { // 当前值小于目标值进制太小了 low mid 1; } } if (ans -1) cout Impossible; else cout ans;5. 边界条件与魔鬼测试数据这道题的所有“坑”几乎都体现在边界数据上。下面我列举几组极具代表性的测试数据并解释它们如何挑战我们算法的鲁棒性。测试数据1一位数字的特例输入 1 1 1 10 解释 N1”1”(十进制)求N2”1”的进制。 输出 2我们的算法中对于一位数low max(2, 11) 2。因为target(1) val(1)所以直接输出low2。注意这里不能进入二分因为一位数不满足单调性在任意进制下值恒为1二分逻辑会失效。测试数据2目标值小于下限输入 3 4 1 10 解释 N1”3”(十进制)求N2”4”的进制。low max(2, 41)5。 逻辑 N2”4”在大于等于5的进制下其值至少为4。而目标值是34 3。所以即使使用最小进制5值也大于目标值无解。 输出 Impossible我们的二分算法能处理吗low5,highmax(5,3)16。首先尝试进制5cmp(“4”, 5, 3)计算4 3返回1说明当前值大于目标值。于是high调整为mid-14此时low5 high4循环结束ans仍为-1输出Impossible。正确。测试数据3大数溢出与精确上界输入 1000000000 1000000000 1 10 解释 N1”1000000000”(十进制)求N2”1000000000”的进制。这是一个性能与溢出检测的双重考验。low2。如果我们粗暴地将high设为target1即1000000001二分查找大约需要log2(1e9) ≈ 30次迭代每次迭代的cmp函数需要遍历10位数字完全可接受。关键在于cmp函数中的溢出判断if (sum 0 || sum target)能有效工作。当mid很大时sum可能在第一次或第二次乘法时就溢出变负从而快速返回1指示high减小。测试数据4解恰好是target输入 100 10 1 10 解释 N1”100”(十进制)求N2”10”的进制。显然10在十进制下就是100不对10在十进制下是10。等等我举错例子了。应该是N1”100”, N2”100”, tag1, radix10。求N2的进制使得其值等于100。答案是10。但这里有个陷阱N2”100”low max(2, 1)2。target100。我们的上界high max(2, 100)1 101。二分查找会找到10。没问题。测试数据5解非常大且target很小输入 1 abcdefghij 1 10 解释 N1”1”(十进制)求N2”abcdefghij”的进制。这是一个10位的字符串每位都是最大值’j’代表35。low max(2, 351)36。要使这个巨大的数在某个进制下等于1这显然是不可能的除非进制趋于无穷大不随着进制增大这个数的值会飞速增长不可能等于1。所以无解。我们的算法low36,target1,highmax(36,1)137。在进制36下cmp函数计算这个数的值第一位 ‘a’10,sum10已经大于target1立刻返回1。于是high减小最终low始终大于high找不到解。正确。测试数据6解的上界需要大于target考虑 N1”10” (十进制) N2”10”。求N2的进制。显然解是10。target10,low2。如果我们设high target 1 11二分区间是[2,11]能覆盖到10。但如果设high target呢区间是[2,10]也能覆盖。但考虑 N1”17”, N2”11”。求N2的进制。target17。N2”11”在16进制下是17。解是16。high target118能覆盖16。high target17也能覆盖。看起来high target似乎也行但考虑 N1”100”, N2”99”。求N2的进制。target100。N2”99”在101进制下是9*1019918已经大于100。实际上”99”在进制r下的值是9r9令其等于100解得r91/9不是整数无解。但我们需要确保二分区间足够大以包含所有可能解。一个反例是当未知数非常短而目标值非常大时解可能大于target。例如target1000000,N2”10”。令10在进制r下的值等于1000000即1*r^1 0 r 1000000。解就是1000000等于target。所以high需要至少为target。另一个例子target100,N2”20”。解是2*r 0 100r50。解50小于target。综合来看high设为max(low, target) 1是一个简单安全的策略它确保了当可能解radix target时区间能覆盖。当可能解radix target1时如一位数情况targetval, 解是val1区间也能覆盖。当可能解radix target1时这种情况存在吗假设target5,N2”12”。解是1*r 2 5r3。解小于target。似乎解不会大于target1考虑target很小N2是多位数且低位数字很大。例如target6,N2”15”。1*r 5 6r1不合法。N2”24”2*r46r1不合法。实际上对于两位数ab值a*r b。要使a*r b target且r max(a,b)1则r (target - b) / a。由于a1,b0要使r target需要(target-b)/a targettarget-b a*target-b (a-1)*target这不可能成立因为左边非正右边非负。所以对于两位数解不可能大于target。对于更多位数随着位数增加值增长更快解更不可能大于target。因此high max(low, target) 1是足够安全的。甚至high max(low, target)可能也够但加上1更保险也避免了当low target时二分区间初始为[low, low]而漏掉解虽然这种情况可能不存在。6. 完整代码实现与逐行解析结合以上所有分析下面给出一个考虑周全的C实现。代码包含了详细的注释解释了每个关键步骤的意图和注意事项。#include iostream #include string #include algorithm #include cctype #include climits using namespace std; // 将字符转换为对应的数值 long long charToVal(char c) { if (isdigit(c)) return c - 0; else return c - a 10; // 题目保证字母为小写 } // 安全比较函数计算str在radix进制下的值与target比较 // 返回 -1: 值 target, 0: 值 target, 1: 值 target 或溢出 int cmp(const string str, long long radix, long long target) { long long sum 0; for (char c : str) { sum sum * radix charToVal(c); // 溢出判断如果sum在计算过程中变为负数说明乘法溢出 // 提前终止如果sum已经大于target后续位数只会增加sum肯定大于target if (sum 0 || sum target) { return 1; } } if (sum target) return -1; if (sum target) return 0; return 1; // 实际不会执行到这里 } // 将已知进制字符串转换为十进制数 long long toDecimal(const string str, long long radix) { long long val 0; for (char c : str) { val val * radix charToVal(c); // 已知进制是合法的但为了安全也可以加溢出判断不过题目范围一般不会溢出 } return val; } int main() { string N1, N2; int tag; long long known_radix; cin N1 N2 tag known_radix; // 统一处理让unknown_str代表待求进制的数target_val代表已知数的十进制值 string known_str, unknown_str; if (tag 1) { known_str N1; unknown_str N2; } else { known_str N2; unknown_str N1; } // 步骤1计算目标值target_val long long target_val toDecimal(known_str, known_radix); // 步骤2确定未知数的最小可能进制low long long max_digit 0; for (char c : unknown_str) { long long val charToVal(c); if (val max_digit) max_digit val; } long long low max_digit 1; if (low 2) low 2; // 进制至少为2 // 步骤3处理未知数长度为1的特殊情况 if (unknown_str.length() 1) { long long single_val charToVal(unknown_str[0]); if (target_val single_val) { // 一位数时值恒定。只有当目标值等于该恒定值时才有解。 // 且解的最小进制是low因为low已经保证了进制max_digit而max_digit就是single_val cout low endl; } else { cout Impossible endl; } return 0; } // 步骤4二分查找进制 long long high max(low, target_val) 1; // 上界1是为了确保包含边界 long long ans -1; while (low high) { long long mid low (high - low) / 2; // 防止溢出 int result cmp(unknown_str, mid, target_val); if (result 0) { ans mid; // 找到可行解 high mid - 1; // 尝试寻找更小的解 } else if (result 1) { // 当前进制太大导致值大于目标或溢出 high mid - 1; } else { // 当前进制太小值小于目标 low mid 1; } } if (ans -1) { cout Impossible endl; } else { cout ans endl; } return 0; }关键行解析第48-55行统一变量。这是一个好的编程习惯避免后续逻辑中频繁判断tag。第60-64行计算下界low。注意low必须至少为2这是进制的基本要求。第67-77行处理一位数的特例。这是很多粗心解法遗漏的点。一位数的值不随进制变化必须单独判断。第81行上界high的设定。max(low, target_val) 1是一个经验性公式在实践中被证明是安全且有效的。1确保了当target_val可能就是解时例如一位数情况解是target_val1它被包含在区间内。虽然对于多位数解可能不会大于target_val但加上1也无害且使逻辑统一。第82-95行二分查找循环。注意ans的更新和high的调整。当我们找到一个可行解result0时我们记录它并将上界缩小high mid - 1以继续在左侧寻找更小的解这满足了题目“输出最小进制”的要求。cmp函数中的溢出判断if (sum 0)这是处理大数进制的关键。在long long乘法溢出时行为是未定义的但通常会发生环绕wrap-around导致结果变为负数。利用这一特性进行提前判断是竞赛编程中的常见技巧。7. 常见错误与调试心得即便有了清晰的思路和代码在实现时依然可能遇到各种“坑”。以下是我在调试过程中总结的几个常见错误点错误1上界设置过小这是最经典的错误。例如只将high设为36或者设为target_val。对于像N2”10”,target_val1000000000这样的数据解是1000000000如果上界不够大根本搜索不到。心得永远不要假设进制有一个固定的上限如36。进制的可能范围与目标值紧密相关保守的做法是将其上界设为target_val或target_val1并确保不低于low。错误2忽略一位数的特殊情况对于一位数如N2”5”它在任何进制下的值都是5。如果你用二分法去查找函数f(radix)是一个常数不满足单调性二分查找的逻辑根据比较结果调整low或high会完全失效可能导致死循环或错误答案。心得在二分前务必检查字符串长度。如果长度为1直接进行相等性判断和合法性判断进制必须大于该数字的值。错误3溢出处理不当直接使用long long计算未知数的值在进制很大时必然溢出。溢出后得到的结果可能是负数或一个错误的正数导致比较结果完全不可靠。心得必须实现防溢出的比较函数。在计算过程中一旦中间结果超过目标值target_val就可以立即返回“大于”一旦中间结果溢出变负也立即返回“大于”。这利用了题目只要求比较大小而不需要知道具体超出多少的特性。错误4下界计算错误下界low不是固定的2而是max(2, max_digit 1)。例如数字”1a”最大数字是 ‘a’值10所以进制至少是11。如果错误地将low设为2二分搜索会从2开始在计算”1a”在进制2下的值时会遇到非法数字 ‘a’导致错误。心得在开始任何计算前先遍历一遍字符串找出最大数字字符对应的数值。错误5找到解后未继续搜索最小解题目要求输出最小的可行进制。二分查找找到一个解后不能直接退出因为当前解mid可能不是最小的。心得在cmp返回0时记录答案ans mid然后将搜索区间向左侧缩小high mid - 1继续查找。循环结束后ans中存储的就是找到的最小解。调试这类题目最好的方法就是构造本节第5部分提到的那些边界测试数据用打印日志的方式跟踪low,high,mid,cmp返回值等关键变量的变化观察二分搜索的轨迹是否符合预期。尤其是在cmp函数中可以临时打印sum的值看它是否在溢出前就正确返回。