PAT A1010 Radix (25 分)

Given a pair of positive integers, for example, 6 and 110, can this equation 6 = 110 be true? The answer is yes, if 6 is a decimal number and 110 is a binary number.

Now for any pair of positive integers N​1​​ and N​2​​ , your task is to find the radix of one number while that of the other is given.

Input Specification:
Each input file contains one test case. Each case occupies a line which contains 4 positive integers:

N1 N2 tag radix
Here N1 and N2 each has no more than 10 digits. A digit is less than its radix and is chosen from the set { 0-9, a-z } where 0-9 represent the decimal numbers 0-9, and a-z represent the decimal numbers 10-35. The last number radix is the radix of N1 if tag is 1, or of N2 if tag is 2.

Output Specification:
For each test case, print in one line the radix of the other number so that the equation N1 = N2 is true. If the equation is impossible, print Impossible. If the solution is not unique, output the smallest possible radix.

Sample Input 1:
6 110 1 10
Sample Output 1:
2
Sample Input 2:
1 ab 1 2
Sample Output 2:
Impossible

以下是AC的代码：

#include<cstdio>
#include<string>
#include<algorithm>
#include<iostream>
using namespace std;
const long long INF =(1LL<<63)-1;
int map[256];
void mapinit(){
	for(char c='0';c<='9';c++){
		map[c] = c-'0';
	}
	for(char c='a';c<='z';c++){
		map[c] = c-'a'+10;
	}
}
long long change2dec(string str,long long radix,long long higheset){
	int len = str.size();
	long long ans= 0;
	for(int i=0;i<len;i++){
		ans=ans*radix+map[str[i]];
		if(ans<0||ans>INF) return -1;
	}
	return ans;
}
long long findleft(string str){
	int len = str.size();
	long long ans=-1;
	for(int i=0;i<len;i++){
		if(ans<map[str[i]]) ans=map[str[i]];
	}
	return ans+1;
}
int main(void){
	mapinit();
	string n1,n2;
	long long tag,radix;
	cin>>n1>>n2>>tag>>radix;
	if(tag==2) swap(n1,n2);
	long long num1= change2dec(n1,radix,INF);
	long long leftmin=findleft(n2);
	long long rightmax=max(num1,leftmin)+1;
	long long left=leftmin,right=rightmax,mid,num2;
	bool fnd=false;
	
//	printf("\n--%lld--%lld--%lld--\n",leftmin,rightmax,mid);
	while(left<=right){
		mid=(left+right)/2;
		num2=change2dec(n2,mid,rightmax);
		if(num1==num2){
			fnd=true;
			break;
		}
		else if(num1<num2||num2<0){
			right=mid-1;
		}else left=mid+1;
	}
	if(!fnd) printf("Impossible");
	else printf("%lld",mid);
	
	return 0;
} 

思路：
这道题看起来不难，实际上令人吐血（其实我连续这几天没有发记录就是因为打开书就被这道题劝退了）.
题意简单来说，就是让你找 让两个数字相等的进制 (radix) 。如果你马上开始用暴力枚举，会有测试点无法通过；同时你看着这道题 多达19 个的测试点，可能心里还不知道自己面对的是什么。
然后你于是灵机一动，想用二分法来做。如何确认二分法的上下界呢？ 这里又有需要注意的地方，首先可能的下界不难，将 n2 中出现过最大的字符 +1就是可能的最小下界。
上界我开始以为是36，因为 a - z 代表 10 - 35，所以可以表示的最大进制应该是36.（这个思路显然是有问题的，因为 36 以上的进制 n2也能表示出来，比如100 在99进制下代表99^ 2）。果然很多测试点都通不过，只有几分。
实际上这里，测试点中的，最大的进制可能是 int的边界最大值，也就是 2^ 32-1. 这个数量级的进制肯定会让转化为10进制过程中的数字溢出了。所以这里必须要对溢出的情况进行处理。首相定义了long long INF = (1LL<<63)-1; 代表long long 类型下的最大值，超过这个值就会变成负数。所以溢出可以表达为： num<0 || num>INF.
此外还应该注意，如果num2转化出来溢出了，可能是num2 现在的进制太小了，所以 也应该归类到 right= mid-1；的情况中。具体可以参考上面的代码。