共计 1871 个字符，预计需要花费 5 分钟才能阅读完成。
这道题而可以说是比较难的一道题，如果采用常规遍历，会出现时长或者溢出的问题；示例中给出的思路很值得借鉴；个人通过该示例有以下几个不同理解：1. 有时候两个不同进制的数对比，我们可以进行进制，转化十进制来进行比较；2. 对于有些枚举或者寻找问题，为了不进行枚举遍历，我们应该第一时间想到二分查找；
对于第一点，这个在题目中有所体现，我们都是将其转化为相应的十进制下，然后进行比较，看是否相同；在这个途中，有个难点：对于未知进制数，我们应该如何推断，一定要注意溢出问题；
在本题目中，并没有对进制有限定，如果按照常规进制计算，就会发生 int 或这 longlong 溢出，这一点要注意；而对于未知进制数，我们就可以让二分派上用场；本题目的根本就是进制枚举，所以我们可以规定进制的上界和下界，从而通过二分来寻找一个进制，使得通过改进之转换的数和给定的数相同，来达到最终的结果；
那么问题又来了，上界和下界如何确定？下界好说，下界就可以取整个数字序列中最大的数，加一就是下界。例如对于一个位 15，最起码应该是 16 进制；
而对于上界，比较难以理解，上界取另一个数字在十进制下的值，加一就是上界；举个例子说明一下，假如另一个数字十进制下是 156，如果当前给出的值是 1，那么多少进制可以让其和 156 相等，答案就是 156 进制，由于在二分查找下，我们输入的序列大原本序列 1 位，所以还需要 +1；
详细代码如下所示：
#include<iostream>
#include<stdlib.h>
#include<stdio.h>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long LL;
LL inf=(1LL<<63)-1;
char n1[20],n2[20],temp[20];
int m[256];
void init(){
for(char c=’0′;c<=’9′;c++){
m=c-‘0′;
}
for(char c=’a’;c<=’z’;c++){
m=c-‘a’+10;
}
}
LL convert2num10(char a[],LL radix,LL t){
LL ans=0;
int len=strlen(a);
for(int i=0;i<len;i++){
ans=ans*radix+m[a[i]];
if(ans<0||ans>t)
//ans<0 为大到溢出的情况
return -1;
}
return ans;
}
int findLargestDigit(char N2[]){
int ans=-1;
int len=strlen(N2);
for(int i=0;i<len;i++){
if(m[N2[i]]>ans){
ans=m[N2[i]];
}
}
return ans+1;
}
int cmp(char n2[],LL radix,LL t){
int len=strlen(n2);
LL num=convert2num10(n2,radix,t);
if(num<0)
return 1;
if(t==num)
return 0;
else if(t>num)
return -1;
else
return 1;
}
LL binarySearch(char n2[],LL left,LL right,LL t){
LL mid;
while(left<=right){
mid=(left+right)/2;
int flag=cmp(n2,mid,t);
if(flag==0)
return mid;
else if(flag==-1)
left=mid+1;
else
right=mid-1;
}
return -1;
}
int main(){
init();
int tag,radix;
scanf(“%s%s%d%d”,n1,n2,&tag,&radix);
if(tag==2){
strcpy(temp,n1);
strcpy(n1,n2);
strcpy(n2,temp);
}
LL t=convert2num10(n1,radix,inf);
// 将 N1 从 radix 进制转化为 10 进制；
LL low=findLargestDigit(n2);
//low 是序列中最大的数，也就是可以比较的最小进制，例如 110，则合法的进制最小都未进制
LL high=max(low,t)+1;
//high 是上界
LL ans=binarySearch(n2,low,high,t);
if(ans==-1)
printf(“Impossible\n”);
else
printf(“%lld\n”,ans);
system(“pause”);
return 0;
}
