1. 从一道25分题说起为什么Radix值得反复琢磨PAT甲级里25分的题不少但能让人做完之后回头再看三遍的1010 Radix绝对算一个。这道题表面上是进制转换实际上考的是二分查找的边界处理、大数溢出的判断、以及一个很多人第一次做都会忽略的坑——进制的上界到底怎么定。我第一次做这道题的时候写了不到四十行代码样例全过提交上去只有一半的测试点绿了。后来花了整整一个下午才把那些飘红的测试点一个个啃下来。这道题的核心场景是这样的给你两个数告诉你其中一个是另一个在某个未知进制下的表示问你这个未知进制最小是多少。如果不存在这样的进制输出Impossible。听起来不复杂但真正动手写的时候你会发现几个要命的问题进制可以大到什么程度转换过程中怎么判断溢出为什么不能用暴力枚举适合读这篇内容的人包括正在刷PAT准备甲级考试的同学、想巩固二分查找和进制转换基本功的开发者、以及任何对边界条件处理感兴趣的人。不管你是刚接触算法题的新手还是已经刷了几百道题的老手Radix这道题都能让你在某些细节上重新审视自己的代码习惯。我写这篇东西的目的很简单把这道题从读题到AC的完整思考链路摊开来讲包括我踩过的坑、想错的思路、以及最后总结出来的那套稳定解法。你不需要有很强的算法背景只要能写基本的循环和判断就能跟着走下来。2. 题目到底在问什么把自然语言翻译成数学条件2.1 输入输出的真实含义题目给的输入格式是N1 N2 tag radix。N1和N2是两个字符串形式的数tag是1或2radix是一个整数。如果tag等于1说明N1是在radix进制下的表示要找N2在什么进制下等于N1的值如果tag等于2反过来。这里第一个容易读错的地方是radix是已知那个数的进制不是未知那个数的进制。我见过有人把tag和radix的关系搞反了结果代码逻辑整个拧过来样例能过但隐藏测试点全挂。输出要求是如果存在这样的进制输出最小的那个如果不存在输出Impossible。注意是最小的进制不是任意一个。这个“最小”两个字直接决定了我们后面要用二分查找而不是随便找一个可行解。2.2 进制转换的数学本质一个字符串在某个进制下的值计算方式是从最高位到最低位每一位的数字乘以进制的对应次幂然后求和。比如“123”在十进制下是1×10²2×10¹3×10⁰123。在任意进制r下“123”的值是1×r²2×r¹3×r⁰。这个计算过程本身不复杂但问题在于当r很大的时候r²、r³这些项会迅速膨胀超出64位整数的表示范围。C里long long最大大约是9.22×10¹⁸而题目中radix可以大到36的10次方这个量级转换过程中很容易溢出。所以核心矛盾就出来了我们要在一個可能非常大的范围内寻找一个满足等式的进制值同时还要在计算过程中防止溢出导致的错误判断。2.3 为什么暴力枚举不可行最朴素的想法是从某个下界开始逐个进制去试看哪个能让两个数相等。但题目中进制的上界可以到多少如果已知数的值很大未知数的位数又很少那么未知数的进制可能需要非常大才能匹配上。举个例子已知数在十进制下是10¹⁸未知数只有一位“1”。那么未知数的进制就是10¹⁸。如果你从2开始一个一个试试到10¹⁸那显然超时。所以必须用二分查找把线性搜索变成对数搜索。3. 二分查找的上下界这道题最容易翻车的地方3.1 下界怎么定不只是最大数字加一未知数的进制下界直觉上应该是“这个数中出现过的最大数字加一”。比如未知数是“19”最大数字是9那么进制至少是10因为9在9进制下是不合法的。但这个直觉有一个漏洞如果未知数只有一位比如“5”最大数字是5下界是6。这没问题。但如果未知数是“0”呢最大数字是0下界是1但进制至少是2才合理。所以下界应该是max(最大数字1, 2)。还有一个更隐蔽的情况如果未知数只有一位且这一位的数字是d那么它在任何大于d的进制下值都是d。这意味着如果已知数的值恰好等于d那么所有大于d的进制都满足条件我们要输出最小的那个也就是d1。这个逻辑如果不处理好会漏掉一些测试点。3.2 上界怎么定一个容易想当然的错误很多人第一次做这道题会把上界设成36因为题目说进制范围是2到36。但这是错的。题目原文说的是“for the purpose of this problem, the radix of a number is between 2 and 36”但这是对已知数的radix的限制不是对未知数的限制。未知数的进制可以超过36。那上界到底应该设多少一个安全的做法是上界设为已知数的值加一。因为如果未知数的进制大于已知数的值那么未知数的值至少是1×r⁰1如果只有一位或者更大。实际上当未知数只有一位时它的值就是那一位的数字与进制无关只要进制大于那个数字。所以如果已知数的值小于未知数的那一位数字就不可能相等。更准确地说上界可以设为max(已知数的值, 下界)1。但已知数的值可能很大计算过程中可能溢出。所以我们需要在二分查找的过程中动态判断。3.3 二分查找的终止条件与溢出处理二分查找的框架很简单left下界right上界每次取mid计算未知数在mid进制下的值与已知数比较。如果相等记录答案并尝试更小的进制如果小于说明进制太小leftmid1如果大于说明进制太大rightmid-1。但问题在于计算未知数在mid进制下的值时可能会溢出。如果溢出说明mid进制太大了应该往小找。所以我们需要一个安全的转换函数它在发现值超过已知数时立即返回一个标记而不是继续计算导致溢出。这里有一个细节已知数的值本身也可能溢出。如果已知数在它的radix进制下转换出来就超过了long long的范围那这道题就没法用long long做了。但实际上PAT的测试数据不会这么变态已知数的值在long long范围内。不过为了保险转换函数应该用unsigned long long或者加上溢出判断。4. 手把手写代码从框架到细节的完整实现4.1 核心转换函数的写法先写一个函数把字符串在给定进制下转成数值同时检测溢出。这里用long long并且在每一步乘法之前判断是否超过一个安全阈值。long long convert(string s, long long radix, long long limit) { long long value 0; for (char c : s) { int digit (c 0 c 9) ? c - 0 : c - a 10; if (digit radix) return -1; // 非法数字 if (value (limit - digit) / radix) return -1; // 溢出 value value * radix digit; } return value; }这个函数里limit是已知数的值。如果转换过程中value超过了limit直接返回-1表示溢出。这样我们就不需要担心long long溢出了。4.2 二分查找的完整逻辑long long findRadix(string unknown, long long target) { char maxDigit *max_element(unknown.begin(), unknown.end()); long long low max(2LL, (long long)(maxDigit 0 maxDigit 9 ? maxDigit - 0 : maxDigit - a 10) 1); long long high max(target, low) 1; long long ans -1; while (low high) { long long mid low (high - low) / 2; long long val convert(unknown, mid, target); if (val target) { ans mid; high mid - 1; } else if (val 0 || val target) { high mid - 1; } else { low mid 1; } } return ans; }这段代码里high的初始值设为max(target, low)1。为什么加一因为如果target恰好等于low-1那么high至少要是low否则循环不执行。加一是为了覆盖target很小的情况。4.3 主函数的组装与tag的处理主函数里根据tag决定哪个是已知数、哪个是未知数。如果tag1已知数是N1未知数是N2如果tag2反过来。然后把已知数转成数值调用findRadix。int main() { string n1, n2; int tag; long long radix; cin n1 n2 tag radix; string known (tag 1) ? n1 : n2; string unknown (tag 1) ? n2 : n1; long long target convert(known, radix, LLONG_MAX); long long ans findRadix(unknown, target); if (ans -1) cout Impossible; else cout ans; return 0; }这里convert的limit传LLONG_MAX因为已知数的转换不需要限制它本身就在long long范围内。5. 那些让我调试到凌晨的边界情况5.1 未知数只有一位且等于已知数这是最经典的坑。比如已知数是“10”在十进制下等于10未知数是“a”。a在11进制下等于10在12进制下也等于10在任意大于10的进制下都等于10。我们要输出最小的也就是11。但如果你的二分查找在找到11之后继续往左找可能会找到10而10进制下a是非法数字因为a代表10进制必须大于10。所以convert函数里的非法数字判断必须返回-1并且在二分中把-1当作“太大”处理。5.2 已知数转换时就溢出了虽然PAT的数据一般不会这样但如果你自己测试时用了很大的radix已知数转换可能溢出。这时候target会变成一个负数或者错误的值。解决办法是在convert里用limitLLONG_MAX并且在乘法前判断。5.3 二分查找的mid计算溢出low (high - low) / 2这个写法是为了防止lowhigh溢出。如果high本身接近LLONG_MAXlowhigh就会溢出。这个细节很多人不注意但在极端测试点下会挂。5.4 进制上界的动态调整有些人的代码把high设成一个固定的很大的数比如10¹⁸。这样虽然能过但二分次数会多几次。更好的做法是动态计算一个合理的上界。我通常用max(target, low)1这样既安全又高效。6. 从AC到举一反三这道题教给我的通用套路Radix这道题表面上考的是进制转换实际上训练的是几种通用的算法思维。第一种是“把搜索空间参数化”把问题转化成在一个有序范围内找满足条件的值。第二种是“在计算过程中提前终止”避免溢出导致的错误判断。第三种是“边界条件的系统化处理”把下界、上界、非法输入、溢出这些情况都考虑到。我在实际工作中遇到过类似的场景比如在一个很大的配置空间里找满足某个性能指标的最小配置或者在一个时间范围内找满足条件的最小时间戳。这些问题的结构和Radix几乎一样有一个单调的判定函数需要找最小满足值同时判定过程中可能遇到数值溢出或非法输入。如果你能把Radix这道题吃透以后再遇到“找最小满足条件的值”这类问题基本可以套用同样的框架确定搜索范围、写判定函数、二分查找、处理边界。这套思路在算法题里通用在实际工程里也通用。最后说一个我自己的习惯每次做完一道有坑的题我会把坑点单独记下来过一周再重做一遍。Radix这道题我重做了三次第三次才做到一次性AC。那些坑点不是靠看题解能记住的必须自己踩过、调试过、改过才能真正变成自己的东西。