|
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 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 tagis 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具体的取值范围，只给定了位数不超过10，不能随意用Int或long，因为进制没限定范围，可能取值从最低二进制到无穷进制都有可能。
2、考虑的做法是把n1，n2从字符串打成字符数组，再把每一位转成Int，一个大的数就变成了一个Int型的数组。
3、Java中根据Int型的数组，求它十进制的和，可以用BigInteger这个类。new BigInteger(String str,int radix)，把radix进制表示的str这个数转成一个十进制的BigInteger，radix不写默认是十进制表示。
4、radix的下限是，至少比待求的这个数中每一位的最大值大1，上限是各个位按进制累加之后，其值不能大于已经给定具体大小的那个数。
5、用暴力算法的话，从下限遍历到上限，速度太慢，所以考虑用二分法。
6、程序中先用了暴力算法从radix的下限计算到了1000，1000之后用暴力算法，主要是为了调试用的。边界最小情况就是，待求的那个数只有一位，这时候，任何比这个数大的进制都可以，这时候就输出满足条件的最小的进制。比如 12 c 1 10，答案是13进制。
7、经过多次提交，判断出测试点7的radix，是在long的范围内。其实更严格的话，要把radix也作为一个BigInteger来算。
8、用一个或多个空格（包含制表符tab）分割一个字符串，str.spilt（\\s+); s表示空格，+表示多个，双反斜杠。用 . 分割的话，要用双反义，即（“\\ . ”)。
import java.math.BigInteger;
import java.util.Scanner;
public class Demo2 {
public static void main(String[] args) {
// TODO Auto-generated method stub
Scanner in = new Scanner(System.in);
String n1 = in.next();
String n2 = in.next();
int tag = in.nextInt();
String radix = in.next();
char[] c1 = n1.toCharArray();
char[] c2 = n2.toCharArray();
int[] i1 = new int[c1.length];
int[] i2 = new int[c2.length];
for (int i = 0; i < c1.length; i++) {
if (c1[i] >= 'a') {
i1[i] = (10 + c1[i] - 'a');
} else
i1[i] = c1[i] - '0';
}
for (int i = 0; i < c2.length; i++) {
if (c2[i] >= 'a') {
i2[i] = (10 + c2[i] - 'a');
} else
i2[i] = c2[i] - '0';
}
if (tag == 1) {
BigInteger num1 = toDecimal(i1, radix);
judge(num1, i2);
} else {
BigInteger num2 = toDecimal(i2, radix);
judge(num2, i1);
}
}
private static void judge(BigInteger num1, int[] i2) {
// TODO Auto-generated method stub
int min_radix = 2;
BigInteger sum = BigInteger.valueOf(0);
int count = i2.length;
for (int i = 0; i < i2.length; i++) {
if (i2[i] >= min_radix)
min_radix = i2[i] + 1;
}
long radix = min_radix;
while (true) {
BigInteger result = arr_sum(i2, radix);
if (result.equals(num1)) {
System.out.print(radix);
break;
} else if (result.compareTo(num1) > 0) {
System.out.print("Impossible");
break;
} else {
radix++;
if (radix > 1000) {
binarySearch(radix, i2, num1);
break;
}
}
}
}
private static void binarySearch(long radix, int[] i2, BigInteger num1) {
// TODO Auto-generated method stub
long lo = radix;
long hi = Long.MAX_VALUE;
radix = (hi-lo) / 2+lo;
while (true) {
BigInteger result = arr_sum(i2, radix);
if (result.equals(num1)) {
System.out.print(radix);
break;
} else if (result.compareTo(num1) > 0) {
hi = radix - 1;
} else {
lo = radix + 1;
}
radix = (lo + hi) / 2;
if (lo > hi) {
System.out.print("Impossible");
break;
}
}
}
private static BigInteger arr_sum(int[] i2, long radix) {
// TODO Auto-generated method stub
BigInteger sum = toDecimal(i2, radix + "");
return sum;
}
private static BigInteger toDecimal(int[] num, String radix) {
// TODO Auto-generated method stub
BigInteger sum = BigInteger.valueOf(0);
int count = num.length;
BigInteger rad = new BigInteger(radix);
for (int i = 0; i < num.length; i++) {
BigInteger temp = rad.pow(count - 1);
count--;
sum = sum.add(temp.multiply(BigInteger.valueOf(num[i])));
// sum = sum.add(BigInteger.valueOf(num[i] * (int) Math.pow(radix2, --count)));
}
return sum;
}
}
| 
转播
