PAT -- 甲级1010（1010 Radix）

1010 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$

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:

Sample Input 2:

1 ab 1 2

Sample Output 2:

Impossible

给四个数N1，N2，tag，radix分别表示数字1，数字2，选择的数字（1或2），选择的数字的进制，问没被选择的那个数字是否存在一个基数使得两个数的十进制值相等，是的话输出改基数（进制），其中N1、N2用0~9、a ~ z表示0 ~ 35。

思路：二分查找，上界是选择的数字的值+1，下届则是未被选择的数字中最大的那个位+1。注意由于在二分搜索中计算的数字可能会爆long long，所以记得上溢出的时候这种基数策略一定不合法！

Code：

#include <iostream>
#include <string>
#include <algorithm>
#include <cmath>
#include <string.h>
#include <stdio.h>

using namespace std;
const int maxn = (int)1e6+5;
typedef long long LL;

//tag = 1 N1 tab = 2 N2
string N1, N2;
int tag, radix;
LL standard;

LL change (string& pattern, LL k) {
	LL res = 0, s = 1;
	for (int i = pattern.size() - 1; i >= 0; i--) {
		if (pattern[i] >= 'a' && pattern[i] <= 'z') {
			res += (10 - 'a' + pattern[i]) * s;
		} else {
			res += (pattern[i] - '0') * s;
		}
		s *= k;
		if (res < 0) {
			return -1;
		}
	}
	return res;
}

LL max(LL a, LL b) {
	return a > b ? a : b;
}

LL find (LL l, LL r) {
	LL mid, k;
	while (l <= r) {
		mid = l + ((r - l) >> 1);
		k = change(N2, mid);
		if (k == standard) {
			return mid;
		} else if (k < 0 || k > standard) {
			r = mid - 1;
		} else {
			l = mid + 1;
		}
	}
	return -1;
}

int main() {
	LL s;
	cin >> N1 >> N2 >> tag >> radix;
	if (tag == 2) swap(N1, N2);
	standard = change(N1, radix);
	LL l = 0, r = standard;
	for (int i = 0; i < N2.size(); i++) {
		if (N2[i] >= 'a' && N2[i] <= 'z') {
			l = max(l, N2[i] - 'a' + 10);
		} else {
			l = max(l, N2[i] - '0');
		}
	}
	s = find(l + 1, r + 1);
	if (s == -1) {
		cout << "Impossible" << endl;
	} else {
		printf("%lld\n", s);
	}
	return 0;
}