Given a pair of positive integers, for example, 6 and 110, can this equation 6 = 110 be true? The answer is yes, if 6 is a decimal number and 110 is a binary number.
Now for any pair of positive integers N1 and N2 , your task is to find the radix of one number while that of the other is given.
Input Specification:
Each input file contains one test case. Each case occupies a line which contains 4 positive integers:
N1 N2 tag radix
Here N1 and N2 each has no more than 10 digits. A digit is less than its radix and is chosen from the set { 0-9, a-z } where 0-9 represent the decimal numbers 0-9, and a-z represent the decimal numbers 10-35. The last number radix is the radix of N1 if tag is 1, or of N2 if tag is 2.
Output Specification:
For each test case, print in one line the radix of the other number so that the equation N1 = N2 is true. If the equation is impossible, print Impossible. If the solution is not unique, output the smallest possible radix.
Sample Input 1:
6 110 1 10
Sample Output 1:
2
Sample Input 2:
1 ab 1 2
Sample Output 2:
Impossible
给出两个数N1,N2，给出其中一个数N1或N2的进制（输入数据中tag=1表示这这是给出的是N1的进制，tag=2表示给出的是N2的进制），为第二个数寻找合适的进制，使得 两者转换成10进制后的结果相等。输出找到的radix，如果不存在这样的进制，那就输出 ”Impossible“
N1和N2的长度最多为10，每个位置上的数字可以是 0-9 或 a-z，其中 a-z数字 10-35
注意：
每个数长度最多为10，每个位置大小都可以是0-35，那么int肯定是不够存的，比如这个数是zzzzzzzzzz，35 ^ 9 > 2 ^ 32，我们用 long long
并未从题中看出来radix的取值范围（不要自己觉得它最大是35），所以也要定义成 long long才保险。
思路分析相信大家都能想到的是，先把给出的N1或N2（假设给出的进制是N1的进制）按照给出的进制转成十进制，然后从1开始测试每种进制，把N2转成十进制判断是否和N1相等，如不相等就增加进制，继续转换，比较。。。
问题是，如果这个进制存在还好说，我从1开始增加，总能找到那个进制；但是如果它不存在呢？增加到无穷大程序都跑不完。。。。
所以我们必须先确定radix的上限和下限。
（以第一个数进制给出，转换成十进制结果是N1，求N2的进制为例进行说明）
假如N2每个位置上的数字中最大的那个是 x ，那么N2的进制最小是 x + 1，比如你某个位置是0-9，最起码得是10进制吧。
那么它的进制的最大值是多少呢？？那么这个进制最大为 N1
为什么？？？
假如N2只有一位数，假设为x，那么你的进制可以是 比这个数本身大的 任意数字，它所代表的值是 x * 进制 0 = x，所以除非x和N1相等，否则你取啥进制都没办法。
假如N2有两位，那它最小也就是 '1 0'，代表的值是 1 * 进制 1 + 0 * 进制 0 = 进制，所以N2的大小就等于进制的大小，如果你让N2的进制=N1时，N2都不能和N1相等，那么你把进制变得更大，N2转换后必然比N1更大。当N2有更多位时就更不用说了，肯定更不可能，每差一个位置，值就差的更多
所以N2的进制的取值范围是 【N2字符串中最大的那个字符代表的值+1，N1】
确定了进制的取值范围之后，我们可以用for循环进行遍历，但是复杂度比较高，这里我们选取二分法。
注意不要漏掉对溢出情况的判断，若N2在某进制下转换成十进制的结果大于N1，应该缩小右边界；但是，如果N2在某进制下转换成十进制的结果小于0，也要缩小右边界，小于0说明进制太大，它转换后long long都存不下了。
while(low <= high) { long long mid = low + (high - low) / 2; long long temp = convert(numStr, mid); // temp < 0，代表得到的数字越界，temp > target都代表当前进制太大，需要调整上限 if (temp < 0 || temp > target) high = mid - 1; // 当前进制正好 else if (temp == target) return mid; // 当前进制太小 else low = mid + 1; } 完整代码 #include <iostream> #include <algorithm> #include <cmath> using namespace std; /** * 给出两个数n1,n2，给出其中一个数n1及其进制radix，为第二个数寻找合适的进制使得 两者相等 * * 首先，每个数长度最多为10，每个位置大小都可以是0-35，那么int肯定是不够存的，比如这个数是zzzzzzzzzz，35 ^ 9 > 2 ^ 32 * * 加入这个数每个位置上的数字中最大的那个是 x ，那么这个数的【进制最小是 x + 1】，比如你要表示0-9，最起码得是10进制吧 * 那么它的进制的最大值是多少呢？？其实这个是没有限制的，你可以是任意进制，所以我们用了long long来存 * * 但在这个题中，必须要有一个合适的进制使得n2能转为n1，那么这个【进制最大为 n1】 * * 为什么？？？ * * 假如n2只有一位，那么你的进制只要比这个数字大，就可以任意取，随意，但除非你本身和n1相等,否则你取啥进制都没办法， * 因为最后一个位置是最低位，它代表的是 进制 ^ 0 = 1 * * 假如n2有两位，那它最小也就是 10，1 * 进制 + 0 * 进制 ^ 0 = 进制， * 所以n2的大小就等于进制的大小，如果你让n2的进制=n1时，n2都不能和n1相等，那么你把进制变得更大，n2就更不可能转为n1 * 当n2有更多位时就更不用说了，肯定更不可能，每差一个位置，值就差的更多 * * 所以这个进制的取值范围是 【n2字符串中最大的那个字符代表的值+1，n1】，接着利用二分法 * */ // 根据进制，把字符串转为实际数字 long long convert(string numStr, long long radix) { long long res = 0; int exp = 0; // 最低位指数为0 // auto自动判断类型，rbegin()是最后一个字符，rend()是第一个字符 for (auto it = numStr.rbegin(); it != numStr.rend(); ++it) { // '0'-'9'，注意这里要加*才能得到值 if (isdigit(*it)) res += (*it - '0') * pow(radix, exp++); // 'a'-'z' else res += (*it - 'a' + 10) * pow(radix, exp++); } // 返回结果 return res; } // 找到合适的进制，使得numStr在这个进制下 == target long long findRadix(string numStr, long long target) { // 找到字符串形式的n2中最大的那个字符，注意这里要加*才能得到值 char maxChar = *max_element(numStr.begin(), numStr.end()); // 转为数字加1，就是 进制的下限 long long low = (isdigit(maxChar) ? maxChar - '0' : maxChar - 'a' + 10) + 1; // 进制的上限就是 n1 long long high = max(low, target); // 二分法 while(low <= high) { long long mid = low + (high - low) / 2; long long temp = convert(numStr, mid); // temp < 0，代表得到的数字越界，temp > target都代表当前进制太大，需要调整上限 if (temp < 0 || temp > target) high = mid - 1; // 当前进制正好 else if (temp == target) return mid; // 当前进制太小 else low = mid + 1; } // 没找到合适的，返回-1 return -1; } int main() { // 两个数，每个位置是0-9或a-z，a-z代表10-35，每个数最多长度为10，如果是35进制，最大为35 * 35 ^ 9, 大于2^32 string n1, n2; // radix，基数（进制），tag为1代表这个基数针对于第一个数字，tag为2代表这个基数针对第2个数字 int tag; long long radix; cin >> n1 >> n2 >> tag >> radix; long long res = tag == 1 ? findRadix(n2, convert(n1, radix)) : findRadix(n1, convert(n2, radix)); // 不存在这样的进制 if (res == -1) cout << "Impossible"; else cout << res; return 0; }