首页 > 试题广场 >

Radix (25)

[编程题]Radix (25)

热度指数：7082 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

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.

输出描述:

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.

示例1

输入

6 110 1 10

输出

2<br/>Sample Input 2:<br/>1 ab 1 2<br/>Sample Output 2:<br/>Impossible

算法知识视频讲解

Java

偶就要搞开发

pat上需要使用二分查找才能通过测试点7，将转化后得十进制数作为右端点，即可能的最大进制。

import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] input = br.readLine().split("\\s+");
        String N1 = input[0];
        String N2 = input[1];
        if (input[2].equals("2")) {
            String tmp = N1;
            N1 = N2;
            N2 = tmp;
        }
        int radix = Integer.parseInt(input[3]);
        input = null;
        long num = 0L;
        int N1Len = N1.length();
        for (int i = 0; i < N1Len; ++i) {
            char c = N1.charAt(i);
            if (Character.isLetter(c)) {
                num += (c - 'a' + 10) * (long)Math.pow(radix, N1Len - i - 1);
            } else {
                num += (c - '0') * (long)Math.pow(radix, N1Len - i - 1);
            }
        }
        radix = 0;
        int N2Len = N2.length();
        int[] N2Num = new int[N2Len];
        for (int i = 0; i < N2Len; ++i) {
            char c = N2.charAt(i);
            if (Character.isLetter(c)) {
                radix = Math.max(radix, c - 'a' + 11);
                N2Num[i] = c - 'a' + 10;
            } else {
                radix = Math.max(radix, c - '0' + 1);
                N2Num[i] = c - '0';
            }
        }

        long left = radix, right = Math.max(num, left);
        while (left <= right) {
            long mid = left + ((right - left) >> 1);
            long sum = 0L;
            boolean flag = true;
            for (int i = 0; i < N2Len; ++i) {
                sum += N2Num[i] * (long)Math.pow(mid, N2Len - i - 1);
                if (sum > num) {
                    right = mid - 1;
                    flag = false;
                    break;
                }
            }
            if (!flag) {
                continue;
            }
            if (sum == num) {
                System.out.println(mid);
                return;
            } else {
                left = mid + 1;
            }
        }

        System.out.println("Impossible");
    }
}

编辑于 2025-02-12 16:33:03 回复(0)