1.题目
https://pintia.cn/problem-sets/994805342720868352/problems/994805507225665536
2.思路
（1）将已确定进制的数放在N1，将未确定进制的数字放在N2，以便后面进行统一计算。
（2）题目说给的数N1和N2可能有10个数位，最多为三十六进制，即最大的数为36^10（超过int最大范围），于是将N1转换为十进制，使用long long类型存储。
（3）使用二分法：
对于一个确定的数字串，其进制越大，则该数字串转换为十进制的结果越大，所以可以二分N2的进制，将N2从该进制转换为十进制，令其与N1的十进制比较：如果大于N1的十进制，说明N2的当前进制太大——应往左子区间继续二分，小于同理，当二分结束时即可判断解是否存在。
3.代码
#include<iostream> #include<stdio.h> #include<stdlib.h> #include<string.h> #include<algorithm> using namespace std; 二分查找，进制转换，暴力会超时，确定好上下界 LL inf=(1LL << 63)-1; 注意此处是把LL型的1左移63位 typedef long long LL; LL Map[256]; //0~9 a~z 与0~35的对应 LL inf=(1LL << 63)-1; //long的最大值2^63-1 void init(){ for(char c='0';c<='9';c++){ Map[c]=c-'0'; //将0~9映射到Map的0~9 } for(char c='a';c<='z';c++){ Map[c]=c-'a'+10; //将a~z映射到Map的10~35 } } LL convertNum10(char a[],LL radix,LL t){ //将a转化为十进制，t为上界 LL ans=0; int len=strlen(a); for(int i=0;i<len;i++){ ans=ans*radix+Map[a[i]]; //进制转换 if(ans<0 || ans>t) return -1; //溢出或超过N1的十进制 } return ans; } int cmp(char N2[],LL radix, LL t){ //N2的十进制与t比较 int len=strlen(N2); LL num=convertNum10(N2,radix,t); //将N2转换成十进制 if(num<0) return 1; //溢出，肯定是N2>t if(t>num) return -1; //t更大则返回-1 else if(t==num) return 0; //相等则返回0 else return 1; //num更大，则返回1 } LL binarySearch(char N2[],LL left ,LL right ,LL t){ //二分求解N2的进制 LL mid; while(left<=right){ mid=(left+right)/2; int flag=cmp(N2,mid,t); //判断N2转换成十进制后与t比较 if(flag==0) return mid; //找到解，则返回mid else if(flag==-1) left=mid+1; //往右子区间继续查找 else right=mid-1; //往左子区间继续查找 } return -1; //解不存在 } int findLargestDigit(char N2[]){ //求最大的数位 int ans=-1,len=strlen(N2); for(int i=0;i<len;i++){ if(Map[N2[i]]>ans){ ans=Map[N2[i]]; } } return ans+1; //最大的数位为ans，说明进制数的底线是ans+1 } char N1[20],N2[20],temp[20]; int tag,radix; int main(){ init(); scanf("%s %s %d %d",N1,N2,&tag,&radix); if(tag==2){ //交换N1和N2 strcpy(temp,N1); strcpy(N1,N2); strcpy(N2,temp); } LL t=convertNum10(N1,radix,inf); //将N1从radix进制转换成十进制 LL low=findLargestDigit(N2); //找到N2中数位最大的位加1，作为二分下界 LL high=max(low,t)+1; //上界，用更小的进制基数即可 LL ans=binarySearch(N2,low,high,t); //二分 if(ans==-1) printf("Impossible\n"); else printf("%lld\n",ans); return 0; }
4.注意点
（1）使用遍历进制的暴力枚举会超时。
（2）变量尽量使用long long类型；
对未知进制的数在转换成十进制时判断是否溢出（只要在转换过程中某步小于0即为溢出）。
（3）当N1和N2的十进制相同时，输出N2的radix值。
（4）边界处理：N2进制的下界为所有数位中最大的那个加1，上界=max{下界，N2的十进制}+1—假设已知的是N1的进制。
——可以举栗子：N1=6（10进制），N2=110（求是多少进制时和N1的十进制相同），按照上面的上下界则是2~7，2=1+1,7=max{2,6}+1，上界相当于在N1的最大的数位的基础上加1（毕竟题目问的是满足条件的最小进制）。
