二分，不用二分会tle
二分的范围是：
- 左边界是n2中最大的数+1
- 右边界是n1+1（不是36(字母z)）（此时在该进制下可用1位表示）
比如，n1是十进制表示。那n2就可以是用97进制用来表示。
还有为什么是n1+1，这是仅限于当进制小于36的时候。比如，n1是11进制表示，这时候如果不加一，右边界就只能搜到
，实际n2的进制应该是
还要注意radix过大的时候会爆int，因此用long long 存数
if ((double)res * radix + num(c) > 1e16) return 1e18;
神奇的是加上这一句就能把pat过了。
#include<cmath>
#include<string>
#include<iostream>
using namespace std;
typedef long long LL;
int num(char c){
if(isdigit(c))return c-'0';
else return c-'a'+10;
}
LL todec(string n1, LL radix) { //秦九韶算法
LL res = 0;
for (auto c : n1) {
if ((double)res * radix + num(c) > 1e16) return 1e18;//判断是否溢出
res = res * radix + num(c);
}
return res;
}
int main(){
string n1,n2;
int tag,R;
cin>>n1>>n2;
cin>>tag>>R;
if(tag==2)swap(n1,n2);
LL tn1=todec(n1,R);
LL l=0;
for(auto c:n2) l=max(l,(LL)num(c) +1 );
LL r=tn1+1;
while(l<r){
LL mid=l+r>>1;
if(todec(n2,mid)>=tn1)r=mid;
else l=mid+1;
}
LL tn2=todec(n2,l);
if(tn2==tn1) cout<<l;
else cout<<"Impossible";
return 0;
}
