PTA1010 Radix (25 分) 进制转化

本题考察进制的转化问题。

首先要先了解一下本题解法：

如果不限制未知数的进制，直接暴力会超时，所以采用二分查找。

那就必然要找出最小的进制和最大的进制了。

最小进制 ，最大的那位+1

eg： 1231435346 这个数他的最小进制就是最大的那位 6+1=7；所以二分查找的左边界为7

最大进制，已知数的十进制

eg：已知数是100，未知数是 1231435346 ，那么二分查找的右边界就是100；

convert（） 把radix进制的num1转换成10进制的数

public static int convert(String num1,int radix) { 
    	int sum=0;
    	int length=num1.length();
    	for(int i=0;i<length;i++) {
    		char ch=num1.charAt(i);
    		sum+=(ch>='0'&&ch<='9')?(Math.pow(radix,length-1-i)*(ch-'0')):(Math.pow(radix,length-1-i)*(ch-'a'+10));
    	}
    	return sum;
    }

comparsion（）进行二分查找

public static int comparsion(int sum,String num2) {
    	int length=num2.length();
    	int low=0;
    	for (int i=0;i<length;i++) {
    		char ch=num2.charAt(i);
    		low=Math.max(low, (ch>='0'&&ch<='9')?(ch-'0'):(ch-'a'+10));
    	}
    	int high=sum;
    	while(low<=high) {
    		int mid=low+(high-low)/2;
    		int res=convert(num2,mid);
    		if(res==sum)
    			return mid;
    		else if(res>sum)
    			high=mid-1;
    		else
    			low=mid+1;
    	}
    	return -1;
    	}

package pta;
import java.util.*;

public class P_1010 {
	
	public static int convert(String num1,int radix) { 
    	int sum=0;
    	int length=num1.length();
    	for(int i=0;i<length;i++) {
    		char ch=num1.charAt(i);
    		sum+=(ch>='0'&&ch<='9')?(Math.pow(radix,length-1-i)*(ch-'0')):(Math.pow(radix,length-1-i)*(ch-'a'+10));
    	}
    	return sum;
    }
    public static int comparsion(int sum,String num2) {
    	int length=num2.length();
    	int low=0;
    	for (int i=0;i<length;i++) {
    		char ch=num2.charAt(i);
    		low=Math.max(low, (ch>='0'&&ch<='9')?(ch-'0'):(ch-'a'+10));
    	}
    	int high=sum;
    	while(low<=high) {
    		int mid=low+(high-low)/2;
    		int res=convert(num2,mid);
    		if(res==sum)
    			return mid;
    		else if(res>sum)
    			high=mid-1;
    		else
    			low=mid+1;
    	}
    	return -1;
    	}
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner reader=new Scanner(System.in);
		String num1=reader.next();
		String num2=reader.next();
		int cout=reader.nextInt();
		int radix=reader.nextInt();
		if(cout==1) {
			int ans=comparsion(convert(num1,radix),num2);
			if(ans==-1)
				System.out.print("Impossible");
			else
			System.out.print(ans);
		}
		else{
			int ans=comparsion(convert(num2,radix),num1);
			if(ans==-1)
			   System.out.print("Impossible");
			else
			System.out.print(ans);
	}
		reader.close();
	}

}