共计 2449 个字符，预计需要花费 7 分钟才能阅读完成。
此题难度较大，自己写了 3 次，在不借助外在帮忙的状况下最好问题才 21 分，对于第一次尝试的同学，能够临时放弃。
题目粗心:
输出四个整数 N1、N2、tag、radix。其中 tag–1 示意 N1 为 radix 进制数，tag–2 示意 N2 为 radix 进制数。范畴:N1 和 N2 均不超过 10 个数位，且每个数位均为 0 - 9 或 a~z，其中 0~9 示意数字 0~9、a~z 示意数字 10-35.
求 N1 和 N2 中未知进制的那个数是否存在，并满足某个进制时和另一个数在十进制下相等的条件。若存在，则输入满足条件的最小进制: 否则，输入 Impossible.
算法思路：
此题的难点次要有 2 个，一个是 N2 进制数的范畴的确定，一个是在该范畴中搜寻的办法。咱们在这里假如将曾经晓得的进制数设定为 N1，而后如果 tag 等于 2，就让 N1 和 N2 进行替换
对于 N2 进制的范畴确定如下：
第一：对于其下界很显著为其数字中呈现的最大数字加 1，比方 123456789，这个数字起码是 10 进制的，因为呈现了 9
第二：对于其上界的确定比拟没有那么让人容易想到，首先咱们晓得对于 1 位数字，其进制数和其转化为 10 进制数的大小没有任何关系所以其上界就是下界，其次，对于位数大于 1 的数字，想要求出最大的进制数，并且要转化为 10 进制数后和 N1 的十进制数相等，就必须得保障该数字最小，天然就能够发现位数大于 2 位的最小数字就是 10，而想要该数字转化为 10 进制数后和 N1 的十进制数相等，那么 N2 的进制数必须为 N1 的 10 进制数，综上所述，N2 进制数的上界为下界和 N1 的 10 进制数的最大值 。
对于在下界和上界之间搜寻 N2 进制的办法:
咱们晓得当一个数字的进制数被固定的时候, 其十进制数会随着该数字的增大而增大, 当其数字固定的时候, 其十进制数会随着进制数的增大而增大. 那么咱们为了在 N2 的下界和上界中搜寻出一个数字作为 N2 的进制数，使其转化为 10 进制数后和 N1 的十进制数相等, 能够应用二分搜寻的办法查找该进制数. 具体做法为咱们取得其区间中值 mid, 而后将 N2 转化为 10 进制数，如果该数字和 N1 的十进制数相等，输入 mid 并且返回，如果小于 N1 的十进制数，阐明以后的进制数较小，向右子区间搜寻，否则像左子区间搜寻。退出循环后阐明没有搜寻到符合条件的进制数，输入 Impossible
留神点：
1、将 N2 转化为 10 进制数的时候有可能会溢出，必须得判断在进行区间的划分，然而 N1 不会溢出能够不必判断，测试点 6,8,12,13,15,16 考查 N2 溢出问题
2、有人可能会间接将区间设置为 [0,2^63-1], 然而理论测试后果是测试点 0，1，11，18 会谬误得 21 分 (也算是个不错的分数了)，如果下界设置为 1 更加会出错只能失去 14 分，自己也不晓得为什么。
3、题目所说的多个进制数中输入最小的进制数，个人感觉这个条件是没有用的，因为满足不存在数字肯定，进制数不同还能失去十进制数雷同的。
4、暴力搜寻会超时，此题基本上找到上下界，就能拿到 20 分左右。
提交后果：
AC 代码：
#include <cstdio>
#include <algorithm>
#include <vector>
#include <string>
#include <iostream>
using namespace std;
// radix 进制数 num 转化为 10 进制数
long long toDecimal(string num, long long radix){if(num=="0"){return 0;}
long long result = 0;
long long expo = 1;
for (int i = num.size()-1; i>=0 ; --i) {if(num[i]>='0'&&num[i]<='9'){result += (num[i]-'0')*expo;
} else if(num[i]>='a'&&num[i]<='z'){result += (num[i]-'a'+10)*expo;
}
expo *= radix;
}
return result;
}
// 获取 N2 的最小进制数，为其呈现的最大数字加 1
long long getInfRadixOfN2(string N2){
int radix = -1;
for (int i = 0; i < N2.size(); ++i) {
int temp;
if(N2[i]>='0'&&N2[i]<='9'){temp = N2[i]-'0';
} else if(N2[i]>='a'&&N2[i]<='z'){temp = N2[i]-'a'+10;
}
if(temp>radix){radix = temp;}
}
return radix+1;
}
int main(){
string N1,N2;
cin>>N1>>N2;
int tag,radix;
// 这里保障 radix 为 N1 的，查找 N2 的进制数使其最靠近 N1
scanf("%d %d",&tag,&radix);
if(tag==2){
// radix 为 N2 的就替换 N1 和 N2
swap(N1,N2);
}
long long decimalOfN1 = toDecimal(N1,radix);
long long decimalOfN2;
long long left=getInfRadixOfN2(N2);// 测试点 0,6,19 考查,left 写成 7 测试点 0 和 19 会正确
long long right=max(left,decimalOfN1);
long long mid;
while (left<=right){mid = left + (right-left)/2;
decimalOfN2 = toDecimal(N2,mid);
if(decimalOfN1==decimalOfN2){printf("%lld",mid);
return 0;
} else if(decimalOfN2<decimalOfN1&&decimalOfN2>0){// 测试点 6,8,12,13,15,16 考查 N2 溢出问题
left = mid+1;
} else {right = mid-1;}
}
printf("Impossible");
return 0;
}
