本题几个注意点
1、注意进制上限是n2+1
2、用二分法不然会超时
3、统一转换为十进制再比较但可能会溢出
（一开始用的进制方法有一个测试点过不去不知为何）
#include<iostream> #include<math.h> #include<string> #include<sstream> using namespace std; //俩种求十进制的方法结果不同？ long converse(string n,long radix) { long i,result=0; for(i=0;i<n.length();i++) { if(n[i]>='0'&&n[i]<='9') //result+=(n[i]-'0')*pow(radix,exp); result=result*radix+(n[i]-'0'); else // result+=(n[i]-'a'+10)*pow(radix,exp); result=result*radix+(n[i]-'a'+10); //exp++; // cout<<"***"<<radix<<":"<<result<<":"<<i<<endl; } return result; } int maxdigit(string n) { int i; char max; max=n[0]; for(i=1;i<n.length();i++) if(n[i]>max) max=n[i]; if(max>='0'&&max<='9') return max-'0'; else return max-'a'+10; } //可能会溢出 int compare(string a,long b,long radix) { long i,sum=0; for(i=0;i<a.length();i++) { if(a[i]>='0'&&a[i]<='9') //result+=(n[i]-'0')*pow(radix,exp); sum=sum*radix+(a[i]-'0'); else // result+=(n[i]-'a'+10)*pow(radix,exp); sum=sum*radix+(a[i]-'a'+10); if(sum>b||sum<0) return 1; } if(sum<b) return -1; else if(sum==b) return 0; } long findradix(string n1,string n2,long radix,int max) { long r,dn1=-1,dn2,i,l,mid,result=-1; dn2=converse(n2,radix); l=max+1; r=dn2+1; mid=(l+r)/2; int k; while(l<=r) { k=compare(n1,dn2,mid); if(k==-1) { l=mid+1; } if(k==1) { r=mid-1; } if(k==0) { result=mid; r=mid-1; } mid=(l+r)/2; } return result; } int main() { string n1,n2; int tag,max; long res,radix; cin>>n1>>n2>>tag>>radix; if(tag==1) { max=maxdigit(n2); res=findradix(n2,n1,radix,max); } else { max=maxdigit(n1); res=findradix(n1,n2,radix,max); } if(res!=-1) cout<<res; else cout<<"Impossible"; return 0; }
