1010 Radix （25 分）

这应该是第二次做这道题了，但是还是觉得很难。
我知道需要二分，但是没想到radix这个值这么坑，它的最大值可达INT_MAX
虽然查了别人的题目，通过了这道题，但是还有几个地方没有理解。
如果temp也就是给出了基数的这个数，转换为十进制后溢出了，那么后面二分进行判断时，中间位置的数是正数满足temp < res则二分的区间取左半边，这样就查找不到正确的基数了。
对我来说这道题还是挺难的

方法3

#include <iostream>
#include <string>
#include <vector>
#include <cctype>
#include <algorithm>
using namespace std;
typedef long long LL;
LL changeDecimal(string s, LL r){
	LL res = 0;
	int t ;  
	for(auto c: s){
		if(c >= 'a' && c <= 'z') t = c - 'a' + 10;
		else t = c - '0';
		res = res * r + t;
	}
	return res;
}
LL find_low(string s, LL r){
	char c = *max_element(s.begin(), s.end());
	LL low = isdigit(c)? c -'0': c - 'a' + 10;
	return low + 1;
}
int main() {
	LL temp, res, tag, radix;
	string s1, s2;
	cin>> s1 >> s2 >> tag >> radix;
	if(tag == 2){
		swap(s1, s2);
	}
	
	temp = changeDecimal(s1, radix);
	LL l = find_low(s2, radix), r = max(l, temp);
	while(l <= r){
		LL mid = l + r >> 1;
		res = changeDecimal(s2, mid); //为负数则溢出了 
		if(temp == res){
			cout<<mid<<endl;
			return 0;
			//同时溢出以后，还是能比较大小，但是一个溢出，一个没溢出就不能比较大小
		}else if(temp < res || res < 0) r = mid - 1;  
		else l = mid + 1;		
	}
	cout<<"Impossible"<<endl;
	return 0;
}

方法2

进制转换本身是很简单的，但是本题涉及的进制最高可达整形上界，所以暴力查找肯定是不行的，其次二分法上界和下界的确定很关键。
二分查找的进制下界很容易理解，就是字符串中数字的最大值加1，上界假设字符串2的累加和等于字符串1的十进制值res，此时的进制即为所求的进制，故有:
$<munderover> \sum i = 0 l e n 2 - 1 </munderover> s t r 2 [i] * r a d i x^{(l e n 2 - 1 - i)} = r e s$
radix最大取值为res，即上界为res,但是有种特殊情况，就是res为1的时候，此时不管在什么进制下，结果都是1，按照题目要求，需要输出进制最小的那个，所以此时应该输出字符串2中的下界。

#include<cstdio>
#include<cstring>
#include<cmath>
#include<cctype>
typedef long long LL;
LL sum(char s[],int rd){
	int len=strlen(s);
	LL tp=0,t; 
	for(int i=0;i<len;i++){
		if(s[i]>='0'&&s[i]<='9') 
			t = s[i] - '0';
		else
		 	t = s[i] - 'a' + 10;
		tp = tp*rd + t;
	}
	return tp;
}
	
LL max(LL a, LL b){
	return a>b?a:b;
} 
LL findMax(char s[]){
	int len=strlen(s);
	LL temp = -1,t;
	for(int i=0;i<len;i++){
		if(s[i]>='0'&&s[i]<='9') 
			t = s[i] - '0';
		else
		 	t = s[i] - 'a' + 10;
		if(t > temp) temp = t;
	}
	return temp;
}
//使用二分查找加速
LL find(char str1[],char str2[],int r){
	LL tmp=sum(str1,r);
	LL res;
	LL low = findMax(str2)+1, high = max(low,tmp),mid; 
	while(low <= high){
		mid = low + (high - low)/2;
		res = sum(str2, mid);
		if(tmp == res){
			return mid;
		}else if(tmp < res || res < 0){
			 high = mid -1;
		}else {
			low = mid+1; 
		}
	}
	return -1;
}

int main(){
	LL tag,r;
	char str1[15],str2[15];
	scanf("%s%s%lld%lld",str1,str2,&tag,&r);
	LL radix = tag==1? find(str1,str2,r) : find(str2,str1,r);
	if(radix !=-1){
		printf("%lld",radix);
	}else{
		printf("Impossible");
	}
	return 0;
}

方法1

对上界做了进一步优化，这个代码假定字符串2没有给出首位为0的情况，如果希望具有更好的鲁棒性，可以先把字符串转化为数组。
此代码对字符串2只有一个字符的时候，进行了特殊处理。
上界证明请参考这位大佬的博客

#include<cstdio>
#include<cstring>
#include<cmath>
#include<cctype>
typedef long long LL;
LL sum(char s[],int rd){
	int len=strlen(s);
	LL tp=0,t; 
	for(int i=0;i<len;i++){
		if(s[i]>='0'&&s[i]<='9') 
			t = s[i] - '0';
		else
		 	t = s[i] - 'a' + 10;
		tp = tp*rd + t;
	}
	return tp;
}
	
LL findMax(char s[]){
	int len=strlen(s);
	LL temp = -1,t;
	for(int i=0;i<len;i++){
		if(s[i]>='0'&&s[i]<='9') 
			t = s[i] - '0';
		else
		 	t = s[i] - 'a' + 10;
		if(t > temp) temp = t;
	}
	return temp;
}
//使用二分查找加速
LL find(char str1[],char str2[],int r){
	LL tmp=sum(str1,r);
	LL res;
	int len = strlen(str2);
	if(len==1){   //当字符串2只有一位数时0-9，a-z，特殊处理。 
		if(tmp > 35) return -1;
		else return tmp+1;
	}
	LL t = isdigit(str2[0])?str2[0]-'0':str2[0] - 'a' + 10;
	LL low = findMax(str2), high = pow(tmp*1.0/t,1.0/(len-1)) + 1,mid; 
	while(low <= high){
		mid = low + (high - low)/2;
		res = sum(str2, mid);
		if(tmp == res){
			return mid;
		}else if(tmp < res || res < 0){
			 high = mid -1;
		}else {
			low = mid+1; 
		}
	}
	return -1;
}

int main(){
	LL tag,r;
	char str1[15],str2[15];
	scanf("%s%s%lld%lld",str1,str2,&tag,&r);
	LL radix = tag==1? find(str1,str2,r) : find(str2,str1,r);
	if(radix !=-1){
		printf("%lld",radix);
	}else{
		printf("Impossible");
	}
	return 0;
}