【1010】Radix (25分)

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（毕竟题目问的是满足条件的最小进制）。

文章来源: andyguo.blog.csdn.net，作者：山顶夕景，版权归原作者所有，如需转载，请联系作者。

原文链接：andyguo.blog.csdn.net/article/details/103742598