1.该题重点！题目给出N1,N2,tag,Radix，如果tag==1，则radix是N1的进制数，否则为N2的进制数；要求求出另外一个数是否存在在1到36进制中是否有和这个数相等的进制数。
2.最小的radix为t的各位数字最大值+1，否则不合理。
3.采用二分法寻找radix，设初始化l=各位数字最大值+1，r为sInt+1（比源数大1，因为存在t的进制数恰好为sInt+1的情况）。
4.tInt的进制数不一定小于36，题目没有明确说明，只是提到一个digit可以由字母或者数字表示，字母最大表示35，不要误以为这个是最大的radix。
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
AC代码：
//#include<string>
//#include <iomanip>
#include<vector>
#include <algorithm>
//#include<stack>
#include<set>
#include<queue>
#include<map>
//#include<unordered_set>
//#include<unordered_map>
//#include <sstream>
//#include "func.h"
//#include <list>
#include<stdio.h>
#include<iostream>
#include<string>
#include<memory.h>
#include<limits.h>
using namespace std;
int c2int(char c)
{//字符转数字
if (c <= '9'&&c >= '0')
return c - '0';
else if (c <= 'z'&&c >= 'a')
return c - 'a' + 10;
else return 0;
}
int main(void) {
string n1, n2;
int tag;
unsigned long long radix;
cin >> n1 >> n2 >> tag >> radix;
string s, t;
if (tag == 1)
{//tag为1，则radix是n1的进制数
s = n1;
t = n2;
}
else if (tag == 2)
{//tag为2，则radix是n2的进制数
s = n2;
t = n1;
}
unsigned long long sInt = 0;
for (int i = 0; i < s.size(); i++)
{//把s转为十进制
sInt = sInt*radix + c2int(s[i]);
}
unsigned long long minRadix = 2;
for (int i = 0; i < t.size(); i++)
{//求出最小的进制数
minRadix = max(minRadix, (unsigned long long)(c2int(t[i]) + 1));
}
bool flag = false;
unsigned long long result = 0;
unsigned long long r = sInt + 1;//必须+1
unsigned long long l = minRadix;
//使用二分法去查找合适的radix
while (l <= r)//必须要有等号！！
{//从最小的进制数开始遍历
unsigned long long j = (l + r) / 2;//没说明j最大是36进制
unsigned long long tInt = 0;
for (int i = 0; i < t.size(); i++)
{//j为t的进制数，求出t在j进制下的十进制大小
tInt = tInt*j + c2int(t[i]);
if (tInt > sInt)
{//如果尚未统计完，tInt就被sInt大，没必要再统计下去
//说明j进制使得tInt>sInt,t的进制数要比j小
break;
}
}
if (tInt == sInt)
{
flag = true;
result = j;
break;
}
else if (tInt > sInt)
{
r = j - 1;
/*flag = false;
break;*/
}
else l = j + 1;
}
if (flag) cout << result << endl;
else cout << "Impossible" << endl;
return 0;
}