2017-03-02 10:12:38来源:oschina作者:阿豪boy人点击

https://www.patest.cn/contests/pat-a-practise/1010

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

4.在二分查找时，不可直接计算出某个 radix 下数的值，因为可能会 longlong 溢出。于是需要用特定的 compare 函数，在累加的过程中判定是否大于另一个数。算是一种剪枝。
5.还有一个条件：当两个数都是 1 时，输出 2.当两个数相等且不为 1 时，输出题中给出的 radix。 #include
#include
#include
#include
using namespace std;
typedef long long LL;
LL map[256]; //字符与数值的对应 0-9 - 0-9 a-z 与 10-35
const LL INF = (1LL << 63) - 1;
void init() {
for (char c = '0'; c <= '9'; c++)
map[c] = c - '0';
for (char c = 'a'; c <= 'z'; c++)
map[c] = c - 'a' + 10;
}
//将a转换为十进制,t是上界
LL convertNum10(char a[], LL radix, LL t) {
LL ans = 0;
int len = strlen(a);
for (int i = 0; i < len; i++) {
ans = ans * radix + map[a[i]];
if (ans<0 || ans>t) return -1; //溢出或者超过N1的十进制
}
return ans;
}
//N2的十进制与t比较
int cmp(char N2[], LL radix, LL t) {
int len = strlen(N2);
LL num = convertNum10(N2, radix, t); //将N2转换为十进制
if (num < 0) return 1; //溢出,肯定N2>t
if (t > num) return -1; //t较大,返回-1
else if (t == num) return 0; //相等返回0
else return 1; //num较大,返回1
}
//二分求解N2的进制
LL binarySearch(char N2[], LL left, LL right, LL t) {
LL 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 findAns(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; //最大的数位是ans,说明进制数的底线是ans+1
}
char N1[20], N2[20], tmp[20];
int main(int argc, char *argv[]) {
init();
scanf("%s %s %d %d", N1, N2, &tag, &radix);
if (tag == 2) {//交换N1,N2
strcpy(tmp, N1);
strcpy(N1, N2);
strcpy(N2, tmp);
}
LL t = convertNum10(N1, radix, INF);
LL low = findAns(N2);
LL high = max(low, t) + 1;
LL ans = binarySearch(N2, low, high, t);
if (ans == -1)
printf("Impossible/n");
else
printf("%lld/n", ans);
return 0;
}