PAT 甲级【1010 Radix】

2023-10-24 12:40 由 fishcanfly 发表于 #其他

本题范围long型（35)^10
枚举radix范围上限pow(n/a0,1/m)上，考虑上限加1.范围较大。使用二分查找枚举
代码如下

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    @SuppressWarnings("unchecked")
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] words = br.readLine().split(" ");

        String s1 = words[0];

        String s2 = words[1];

        int tag = Integer.valueOf(words[2]);

        long radix = Long.valueOf(words[3]);

        long n1 = 0;
        long n2 = 0;
        long max = 0;

        if (tag == 2) {
            StringBuilder sb = new StringBuilder(s1);
            s1 = s2;
            s2 = sb.toString();
        }
        n1 = get(s1, radix);
        max = getmax(s2);
        long last = -1;
        int m = s2.length();
        long bound = max + 1;
        long upper = max + 1;
        if (m != 1) {
            upper = (long) Math.pow((double) n1 / (select(s2.charAt(0))), 1.1f / (m - 1))+10;
          //  bound = (long) Math.pow((double) n1 / (select(s2.charAt(0)) + 1), 1.1f / (m - 1));
        }
//        bound = Math.max(max + 1, bound);
//

        while (bound <= upper) {
            long mid = (bound + upper) / 2;
            n2 = get(s2, mid);
            if (n2 > n1) {
                upper = mid - 1;
            } else if (n2 == n1) {
                System.out.println(mid);
                return;
            } else {
                bound = mid + 1;
            }
        }
        System.out.println("Impossible");
        return;
    }

    public static long getmax(String s2) {
        long max = 0;
        for (int i = 0; i < s2.length(); i++) {
            long digit = select(s2.charAt(i));
            if (digit > max) {
                max = digit;
            }
        }
        return max;
    }

    private static long get(String s1, long radix) {
        long n1 = 0;
        long base = 1;
        for (int i = s1.length() - 1; i >= 0; i--) {
            long digit = select(s1.charAt(i));
            n1 += digit * base;
            base *= radix;
        }
        return n1;
    }

    public static long select(char ch) {
        if (ch >= '0' && ch <= '9') {
            return ch - '0';
        } else {
            return ch - 'a' + 10;
        }
    }
}