题目描述
链接n1 n2 tag radix
当tag=1时,radix进制的n1的十进制值=ans进制的n2的十进制值,求解这个ans进制是多少。
分析
- 本质就是求解方程!用二分查找求解方程的根
trans(a,radix)==sum
- 先要用longlong类型应该不难看出来。
- 试答案的时候不能顺序搜索,要用二分搜索。
- 二分的边界要想对,最小的应该是数中最小的那个数+1,比如:123a,那么这个数最小的进制数为11(因为数中有a)。最大的边界应该为基准数的十进制值(例如:基准数的十进制为为1000000,另一个数为10,那么它可以是1000000进制的,也满足条件)。
- 如果算的进制数太大时,可能会爆longlong,那么在计算中还要注意对溢出的判断(tmp<0)
#include<bits/stdc++.h>
using namespace std;
string a,b;
int tag,radix;
long long trans(string a, long long radix){ //单增函数
int len = a.size();
long long sum = 0;
for(int i=0;i<len;i++){
if(a[i]>='0' && a[i] <='9')
sum = sum * radix + a[i]-'0';
else sum = sum * radix + a[i]-'a' + 10;
}
return sum;
}
long long findmin(string a){
int len = a.size(), maxnum = 0;
for(int i=0;i<len;i++){
if(a[maxnum] < a[i]) maxnum = i;
}
if(a[maxnum]>='0' && a[maxnum] <= '9') return a[maxnum]-'0' + 1;
return a[maxnum]-'a' + 10 + 1;
}
long long binarysort(string a, long long x){
long long l = findmin(a);
long long r = max(l, x);
while(l<=r){
long long mid = (l+r)>>1;
long long tmp = trans(a,mid);
if(tmp == x) return mid;
else if(tmp > x || tmp < 0) r = mid - 1;
else l = mid + 1;
}
return -1;
}
void solve(){
long long sum, res;
if(tag == 1){
sum = trans(a, radix);
res = binarysort(b, sum);
}else{
sum = trans(b, radix);
res = binarysort(a, sum);
}
if(res == -1) cout<<"Impossible"<<endl;
else cout<<res<<endl;
}
int main(){
cin>>a>>b>>tag>>radix;
solve();
}