PAT 甲级 1010 Radix 二分法+数制转化

Solution：

这道题的意思是：给出两个不超过10位的正数n1、n2，它们的进制可能不一样。题目会给出第一个数或者第二个数的进制，让我们求出另一个数的进制使这两个数相等并输出。如果不存在一个进制使它们相等，则出“Impossible”。基本思想还是二分：我们选择在十进制下比较两个数的大小，先把给出进制的数转化为10进制数，则右边界right就等于这个十进制数，因为如果另一个数的进制比right还大，则它们不可能相等。左边界left就等于没有给出进制的那个数中所有位最大的数+1，因为在n进制下，每位最大是n-1。这样我们就确定了left和right，接下来直接二分就ok了。

代码如下：

//二分
#include<iostream>
#include<algorithm>
#include<math.h>
using namespace std;
typedef long long ll;

ll to_number(char ch){//转换为数字
  if(ch>='0'&&ch<='9'){
    return ch-'0';
  }
  return ch-'a'+10;
}

ll to_decimal(string s,int radix){//转化为十进制
  ll num=0;
  ll ans=1;//ans为每一位要乘的数
  for(int i=s.length()-1;i>=0;i--,ans=ans*radix){
    num=num+ans*to_number(s[i]);
    if(num<0||ans<0){//如果num或者ans爆long long
        return -1;
    }
  }
  return num;
}


int main(){
  string a,b;
  int tag;
  int radix;
  cin>>a>>b>>tag>>radix;//读入数据

  if(tag==2){//如果给出的是第二个数的进制数，交换a，b
    swap(a,b);
  }

  ll base=to_decimal(a,radix);//a的十进制数
  ll right=base;//right=base
  ll left=2;
  ll mid;

  for(int i=0;i<b.length();i++){//求出最小的进制数
    left=max(left,to_number(b[i])+1);
  }

  while(left<=right){
    mid=(left+right)/2;
    ll temp=to_decimal(b,mid);
    if(temp<0||temp>=base){//说明进制大了
        right=mid-1;
    }else{//否则，说明进制小了
        left=mid+1;
    }
  }

  if(to_decimal(b,left)==base){
    cout<<left;
  }else{
    cout<<"Impossible";
  }
  return 0;
}