题意 && 解题思路：
这题题目意思就看了老半天。。。。。。为什么一定要先确认一下N1或者N2的radix？一直傻瓜从2遍历到35不就行了。后来发现=.=原来是我连题目都没看懂，开始就得了6分。一直提交，一直6分。。。。。。想想，N1和N2是不是可以无限大。而且进制很有可能不止到35结束。虽然每一位的数字最大只到z，但是进制不一定啊，比如 ，这样的zyx是完全有可能以36为进制吧。
这道题最关键的是要注意到：不管N1和N2的初始进制是多少，他们最后如果在某个进制上相等了，那他们一起转化成10进制也一定是相等的。
有了这个思路，就可以开始着手写代码了。BufferedReader不是必须的，用Scanner也行，但是这样可以节省一半以上的时间。最难处理的还在二分法处理进制上，不妨假设N1已经确定了进制，N1转化成10进制以后，N2在哪个进制上转化成10进制才和toDecimal(N1)相等呢？暴力遍历明显太慢了，铁头娃（本人）可以试一试，还是本来就慢的java，那就更不行了。在用二分法的时候，需要进一步减少low和high的取值范围，首先low的值肯定会大于N2中最大的一个数字，你想想，如果N2是az，里面有'z'，它是不是必然至少是个36进制的数。对于high的取值，至少是应该>=low的，难道high还会<low吗？是的，首先考虑high的可能最大取值，考虑这样一种极端情况 200 10 1 10，这时N2是不是要在200进制的时候才会和N1相等，high的取值是可能不会超过toDecimal(N1)，但是toDecimal(N1)也可能<low，考虑这样一种情况：9 12 1 10，这时N2是不是在7进制上才和N1相等，但是很明显toDecimal(N1)=9，小于low=9+1=10。尴尬的情况出现了，low<=high<=toDecimal(N1)的同时，又可能low>toDecimal(N1)，所以，high还是老实取Math.max(toDecimal(N1), low)里的最大值吧。想清楚这一点就不难理解此题中的二分法了。
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Main {
public static void main(String[] args) throws IOException{
BufferedReader rd = new BufferedReader(new InputStreamReader(System.in));
String str[] = rd.readLine().split(" ");
long tag = Long.parseLong(str[2]);
long radix = Long.parseLong(str[3]);
String n1= str[0];
String n2= str[1];
long ans = (tag==1) ? toRadix(toDecimal(radix, n1), n2) : toRadix(toDecimal(radix, n2), n1);
if(ans == -1)
System.out.print("Impossible");
else
System.out.print(ans);
}
public static long toRadix(long dec, String n) {
long low = '0';
for (int i = 0; i < n.length(); i++) {
if (low < n.charAt(i)) {
low = n.charAt(i);
}
}
low = ((low>='0' && low<='9') ? low - '0' : low - 'a' + 10) + 1;
long high = Math.max(low, dec);
while(high>=low) {
long mid = (low+high) / 2;
long temp = toDecimal(mid,n);
if(temp == dec) return mid;
else if(temp > dec) high = mid - 1;
else low = mid + 1;
}
return -1;
}
public static long toDecimal(long radix, String n) {
long dec = 0;
for(int i=0; i<n.length(); i++) {
char ch = n.charAt(i);
dec +=
(ch>='0'&&ch<='9') ? Math.pow(radix, n.length()-i-1)*(ch-'0') : Math.pow(radix, n.length()-i-1)*(ch-'a'+10);
}
return dec;
}
}
| 
转播
