题目
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;
}完整代码
代码语言：javascript复制#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;
}
