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 N1 and N2, 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

翻译:
给定一对正数,如:6和100,这个等式6 = 110可以为真吗?答案是“是”,如果6是十进制数,110是二进制数。
现在给你一对正数,你需要找出其中一个数的基数,而另一个数的基数已经给出。
输入:
一行内包括4个正数,N1,N2,tag,radix。N1和N2的位数不超过10位,每一位不超过它的基数,并从集合{0-9,a-z}中选择,其中0-9表示十进制数0-9,而a-z表示十进制数10-35。
最后一个radix代表基数,当tag为1,radix代表N1的基数,当tag为2,radix代表N2的基数。
输出:
在一行内输出那个使N1=N2成立的基数,如果等式不可能成立,输出“impossible",如果结果不唯一,输出最小的基数。
思路:
将每个位对应的十进制值存到数组map中,把已知其基数的N1转为十进制值decinum,取N2的最高位+1为low,另一个数在[low,max(decinum,x)]内取基数去匹配是否等于decinum 
其中选取基数的时候采用二分法,暴力穷举会超时,
注意将值转为十进制时,有可能会因为过大溢出为负数,在进行2分法的时候也要对负数进行判断。


#define _CRT_SECURE_NO_WARNINGS
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int map[256];
char n1[11], n2[11];
int tag, radix;
long long convertToTen(char a[], long long radix) {
	long long ans = 0;
	int len = strlen(a);
	for (int i = 0; i < len; i++) {
		
		ans += map[a[i]] * pow(radix, len - i - 1);
		
	}
	return ans;
}

int cmp(char n2[], long long radix, long long t) {
	int len = strlen(n2);
	long long num = convertToTen(n2, radix);
	if (num < 0) return 1;//当值过大 溢出为负数
	if (num < t) return -1;
	return (t == num) ? 0 : 1;
}

long long binarySearch(char n2[], long long left, long long right, long long t) {
	long long mid;
	while (left <= right) {
		mid = (left + right) / 2;
		int flag = cmp(n2, mid, t);
		if (flag == 0) return mid;
		else if (flag == -1) left = mid + 1;
		else right = mid - 1;
	}
	return -1;
}

int findLargestDigit(char n2[]) {
	int ans = -1, len = strlen(n2);
	for (int i = 0; i < len; i++) { if (map[n2[i]] > ans) { 
			ans = map[n2[i]];
		}
	}
	return ans + 1;
}

int main() {
	scanf("%s%s%d%d", &n1, &n2, &tag, &radix);
	for (char c = '0'; c <= '9'; c++) {
		map[c] = c - '0';
	}
	for (char c = 'a'; c <= 'z'; c++) {
		map[c] = c - 'a' + 10;
	}
	if (tag == 2) {
		swap(n1, n2);
	}
	long long t = convertToTen(n1, radix);
	long long low = findLargestDigit(n2);
	long long high = max(low, t)+1;
	long long ans = binarySearch(n2, low, high, t);
	if (ans == -1) printf("Impossible");
	else printf("%lld", ans);
	return 0;
}