1. 本题范围long型（35)^10
  2. 枚举radix范围上限pow(n/a0,1/m)上，考虑上限加1.范围较大。使用二分查找枚举
  3. 代码如下
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;        }    }}

二分

本页面将简要介绍二分查找，由二分法衍生的三分法以及二分答案。

二分法定义

二分查找（英语：binary search），也称折半搜索（英语：half-interval search）、对数搜索（英语：logarithmic search），是用来在一个有序数组中查找某一元素的算法。

过程

以在一个升序数组中查找一个数为例。

它每次考察数组当前部分的中间元素，如果中间元素刚好是要找的，就结束搜索过程；如果中间元素小于所查找的值，那么左侧的只会更小，不会有所查找的元素，只需到右侧查找；如果中间元素大于所查找的值同理，只需到左侧查找。

性质时间复杂度

二分查找的最优时间复杂度为。

二分查找的平均时间复杂度和最坏时间复杂度均为。因为在二分搜索过程中，算法每次都把查询的区间减半，所以对于一个长度为的数组，至多会进行次查找。

空间复杂度

迭代版本的二分查找的空间复杂度为。

递归（无尾调用消除）版本的二分查找的空间复杂度为