1010 Radix (25分) PAT甲级 Java 实现

1010 Radix (25分) PAT甲级 Java 实现

1 题目

题目链接 https://pintia.cn/problem-sets/994805342720868352/problems/994805507225665536

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

2 解题思路

2.1 题目大意

1. 给你两个数N1和N2，并且告诉你其中一个数的进制，tag为N1和N2的下标，radix是进制

2. 如果两个数相等，让你求另一个数的进制

3. 比如

   6 110 1 10
   

   6是10进制的，问你110和6相等，110是几进制？

2.2 题目细节

1. N1和N2最多10位，每位由0-9以及a-z（分别代表10-35）组成

2. 如果进制不唯一，则输出最小那个

   比如

   1000 8 1 2
   

   1000是2进制的，那么8可以是9进制、10进制…

2.3 解题思路

1. 将两个数都转换成10进制进行比较

2. 代求数的进制可以用二分法寻找

   • 下限是最大位+1

   • 上限是已知数的10进制

     证明上限是已知数的10进制
     设已知数的10进制为a，代求数为b，代求数的十进制为c
     证明：
     (i)如果b只有一位,即b只能是（0-9或a-z)，那么b的进制r∈(b+1,∞)，且b的十进制：c=b*r^0=b此时若a=b，则答案为b+1；若a≠b，则Impossible
     (ii)如果b是2位以上，则最小为10，设b的进制为rc=1*r^1=r<=a∴r的上限为a当b>10(r进制)，则r只能比a小，否则c一定大于a
     

3. 理论上进制可以是任意数，只要大于待求数最大的那位即可，所以有可能非常大，于是用到BigInteger

3 代码

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.math.BigInteger;
public class Main {
    public static void main(String[] args) throws IOException {
    BufferedReader in = new BufferedReader(new InputStreamReader(System.in));String[] s = in.readLine().split(" ");int tag = Integer.parseInt(s[2]) - 1;BigInteger radix = new BigInteger(s[3]);int[] t = buildArray(s[tag]);int[] a = buildArray(s[1 - tag]);BigInteger target = convert(t, radix);BigInteger res = target; //上限为已知数的10进制// BigInteger.valueOf((minRadix(a)));BigInteger temp = convert(a, res);if (target.compareTo(temp) == 0) {
    System.out.print(res);} else if (target.compareTo(temp) > 0 && a.length > 1) {
    // 如果代求数只有一位转成10进制还是它自己，则ImpossiblebinarySearch(a, target, res.add(BigInteger.valueOf(1)));} else {
    System.out.print("Impossible");}}// 用一个数最大那一位来确定其最小进制private static int minRadix(int[] arr) {
    int minr = 0;for (int a : arr) {
    if (a >= minr) {
    minr = a + 1;}}return minr;}// 二分法找进制private static void binarySearch(int[] a, BigInteger target, BigInteger radix) {
    BigInteger lo = radix;BigInteger hi = BigInteger.valueOf(Long.MAX_VALUE);BigInteger mid = lo.add(hi).divide(BigInteger.valueOf(2));while (true) {
    if (lo.compareTo(hi) > 0) {
    System.out.print("Impossible");break;}BigInteger temp = convert(a, mid);if (target.compareTo(temp) == 0) {
    System.out.print(mid);break;} else if (target.compareTo(temp) > 0) {
    lo = mid.add(BigInteger.valueOf(1));} else {
    hi = mid.subtract(BigInteger.valueOf(1));}mid = lo.add(hi).divide(BigInteger.valueOf(2));}  }// 将两个数都用数组存储每一位private static int[] buildArray(String str) {
    int len = str.length();int[] arr = new int[len];for (int i = 0; i < len; i++) {
    char ch = str.charAt(i);if (ch >= '0' && ch <= '9') {
    arr[i] = ch - '0';} else if (ch >= 'a' && ch <= 'z') {
    arr[i] = ch - 'a' + 10;}}return arr;}// 将一个数组表示的数，转换成对应进制的数private static BigInteger convert(int[] a, BigInteger r) {
    int len = a.length - 1;int ex = 0;BigInteger res = BigInteger.valueOf(0);for (int i = len; i >= 0; i--) {
    res = res.add(BigInteger.valueOf(a[i]).multiply(r.pow(ex)));ex++;}return res;}
}