前言

传送门

正文


参考题解

#include<iostream>
#include<algorithm>
#include<cctype>
#include<cmath>
#include<string>
using namespace std;
/* 题意： 要使得满足n1==n2，给出n1或n2的进制，要你求另一个数的进制，如果不存在 一个进制满足n1==n2,则输出Impossible，否则输出能满足条件的最小的进制数 思路：首先将已知进制的数转换为10进制数，考虑到一个数的进制越大，其表示的 10进制数也越大，即具有单调性,故可以使用二分搜索另外一个数的进制（若暴力 遍历每个进制会超时)，而二分最重要的是确定二分范围的上界和下界 ，下界显然 就是待求进制的那个数中最大的元素数值+1，上界则可以使用转化为10进制的后的 数sum 注意点：注意溢出的情况 */

/*将radix进制数str转化为10进制数,之所以用long long是为了防止溢出 (a的每一位分别为0~9或者a~z，其中a~z分别表示10~35)*/
long long toDecimal(string str,int radix){
	long long sum=0;
	int index=0,temp=0;
	for(auto it=str.rbegin();it!=str.rend();it++){
		temp=isdigit(*it)?*it-'0':*it-'a'+10;
		sum+=temp*pow(radix,index++); 
	} 
	return sum;
} 
long long getRadix(string str,long long sum){
	char ch=*max_element(str.begin(),str.end());//获取最大的字符
	long long low=(isdigit(ch)?ch-'0':ch-'a'+10)+1;//二分的下界
	long long high=max(low,sum);//二分的上界 
	/*二分查找算法，如果使用当前进制转化得到数值 比另一个大或者小于0（溢出），说明这个进制太大*/ 
	while(low<=high){
		long long mid=low+high>>1;
		long long temp=toDecimal(str,mid);
		if(temp<0||temp>sum)high=mid-1;
		else if(temp==sum)return mid;
		else low=mid+1;
	} 
	return -1;
}
int main(){
	string n1,n2;
	int  tag=0,radix=0,res;
	cin>>n1>>n2>>tag>>radix;
	res=tag==1?getRadix(n2,toDecimal(n1,radix)):getRadix(n1,toDecimal(n2,radix));
	if(res!=-1)printf("%lld\n",res);
	else printf("Impossible\n"); 
	return 0;
}