此题难度较大，自己写了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的最小进制数，为其呈现的最大数字加1long 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;}