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，不超过10位，以 0-9 表示 0-9， a-z 表示 10-35。已知其中一个数的进制为radix，tag为1表示第一个数，tag为2表示第二个数。求另一个数的进制为多少，可以让N1与N2相等，如果有多个答案输出最小的。
题目分析
假设tag为1，即已知N1的进制为radix。
很多人看到这道题认为直接从2进制枚举到36进制就行了，但实际上题目中并没有限制最大是36进制，题目只是限制了每一位上的数字最大为 z 也就是35，也就是说数字zzz可以是100进制也可以是1000进制，只要大于35即可。
由于可能的进制范围太大，一一枚举肯定会超时，所以我们需要使用二分查找。
二分查找的左边界是什么呢？
对于一个数，它的进制数最小值为max(2 , (每个数位上最大的数 + 1))，比如1a这个数，最小进制为11进制，a+1=11。这就是二分查找的左边界。
那么二分查找的右边界是什么呢？
如果N2长度为1，那么它的进制只要大于等于max(2 , N2 + 1))结果都是相同的。因此N2长度为1时不必进行二分查找，直接按照进制为max(2 , N2 + 1))来计算即可。
如果N2长度大于1，那么这时 N2 的倒数第二位最小是1，这时它的进制只要等于N1 + 1 就有 N2 > N1，所以比N1更大的进制就不用考虑了。这就是二分查找的右边界。
综上所述，分两类情况。
N2长度等于1时，直接判断N2是否和N1相等，如果相等则答案为max(2 , N2 + 1))，不相等则为Impossible。
N2长度大于1时，二分查找N2的进制，范围是[max(2 , (每个数位上最大的数 + 1)), N1]。
当然，也可以不分两种情况，直接在二分到答案时令right = mid - 1然后继续寻找答案，相当于把长度等于1时出现无穷解的情况包含了。
注意事项：数据范围用 int 是不行的；二分时会出现负数的情况，出现负数说明数字太大溢出了。
AC代码
#include <bits/stdc++.h>
using namespace std;
long long f(string s, long long radix) //将radix进制的数转为10进制
{
long long ans = 0;
for (int i = s.length() - 1; i >= 0; i--)
{
int temp = (s[i] <= '9' && s[i] >= '0') ? (s[i] - '0') : (s[i] - 'a' + 10);
ans += temp * pow(radix, s.length() - i - 1);
}
return ans;
}
int main()
{
string n1, n2;
int tag, radix, i, ans = 1 << 30;
long long num1, num2;
cin >> n1 >> n2 >> tag >> radix;
//交换，转换为已知n1的进制，求n2进制
if (tag == 2)
swap(n1, n2);
//将n1计算为10进制赋给num1
num1 = f(n1, radix);
if (n2.length() == 1) //只有长度为1才有可能出现多种答案
{
int value = (n2[0] <= '9' && n2[0] >= '0') ? (n2[0] - '0') : (n2[0] - 'a' + 10);
if (value == num1)
cout << max(2, value + 1) << endl;
else
cout << "Impossible" << endl;
}
else
{
//找出n2中最大的数，加一即为最小可能的进制
char maxch = '0';
for (i = 0; i < n2.length(); i++)
maxch = max(maxch, n2[i]);
int begin = (maxch <= '9' && maxch >= '0') ? (maxch - '0') : (maxch - 'a' + 10);
//二分查找n2的进制
long long left = max(2, begin + 1), right = num1 + 1; //n2倒数第二位至少是1，已经大于num1了，所以进制数最大为num1+1
while (left <= right)
{
long long mid = left + (right - left) / 2;
num2 = f(n2, mid);
if (num1 == num2)
{
ans = mid;
break;
}
else if (num1 < num2 || num2 < 0) //数太大溢出了
right = mid - 1;
else
left = mid + 1;
}
if (ans == 1 << 30)
cout << "Impossible" << endl;
else
cout << ans << endl;
}
return 0;
}