|
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.
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.
6 110 1 10
Sample Output 1:
2
1 ab 1 2
Sample Output 2:
Impossible
题意与分析：
1、N1、N2、tag（1或2）、radix 都是正整数，其中N1、N2 都是十位数，每一位的范围是[ 0 - z ]，也就是[ 0 - 35 ]，这里需要注意的是，虽然每一位的范围是[ 0 - z ]，但并不代表radix最大是36，radix可以非常大，因此radix需要设置为long long型。
2、radix简单地从2开始枚举会超时，需要确定radix的范围二分查找。设N2为未知进制数，那么radix的下界为N2中最大一位数+1，上界为max（下界，N1的值）（N2>=1，若上界>N1，则N2肯定会>N1了，另外N1有可能<下界）。
3、二分查找时，计算某进制下的数值时可能会long long溢出，可以在累加的过程中就判断是否大于另一个数，或者用sum<0判断是否溢出，如是则往左继续二分high=mid-1；若小于另一个数则往右二分low=mid+1；若相等就保存，并继续向左找出最小的符合进制（当某数只有一位时，在所有进制下数值都是相等的）。
#include <iostream>
#include <string.h>
#include <math.h>
#include <map>
using namespace std;
map<char, int> toint;
long long convert(char x[], long long radix) {
int i, j = 0, len = strlen(x);
long long deci = 0;
for(i = len-1; j < len; i--)
deci += toint[x[i]]*pow((long double)radix, j++);
return deci;
}
long long findRadix(char x[], long long deci) {
int i,len;
long long minradix,maxradix,mid,sum;
char max = '1';
len = strlen(x);
for(i = 0; i < len; i++) {
if(x[i] > max)
max = x[i];
}
minradix = toint[max]+1;
maxradix = minradix > deci ? minradix : deci;
while(minradix <= maxradix) {
mid = (minradix + maxradix) / 2;
sum = convert(x, mid);
if(sum < 0 || sum > deci) maxradix = mid-1;
else if(sum < deci) minradix = mid+1;
else return mid;
}
return -1;
}
int main() {
char a[12],b[12],tmp = '0';
int i,index;
long long radix,ret_radix;
//cin >> a >> b >> index >> radix;
scanf("%s %s %d %d",a,b,&index,&radix);
for(i = 0; i < 10; i++) {
toint[tmp] = i;
tmp++;
}
tmp = 'a';
for(i = 10; i < 36; i++) {
toint[tmp] = i;
tmp++;
}
ret_radix = index == 1 ? findRadix(b, convert(a, radix)) : findRadix(a, convert(b, radix));
if(ret_radix == -1)
printf("Impossible");
else
printf("%lld",ret_radix);
return 0;
}
| 
转播
