A1010 Radix （25 分）（二分）（難）

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 N​1​​ and N​2​​, 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
           

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;

typedef long long LL;
LL inf = (1LL << 63) - 1;   //long long的最大值2^63-1
LL m[256];      //将0-9，a-z與0-35對應

void init() {
    for(char c = '0'; c <= '9'; c++) {
        m[c] = c - '0';
    }
    for(char c = 'a'; c <= 'z'; c++) {
        m[c] = c - 'a' + 10;
    }
}

LL convertTo10(char a[], LL radix, LL t) {  //将進制為radix的數組轉化為10進制，t為上界
    LL ans = 0;
    int len = strlen(a);
    for(int i = 0; i < len; i++) {
        ans = ans * radix + m[a[i]];        //進制轉換
        if(ans < 0 || ans > t) {
            return -1;
        }
    }
    return ans;
}

int cmp(char n2[], LL radix, LL t) {        //将N2的十進制與t比較
    int len = strlen(n2);
    LL num = convertTo10(n2, radix, t);
    if(num < 0) {       //N2溢出，肯定是N2 > t
        return 1;
    }
    if(t > num) {       //t比較大，傳回-1
        return -1;
    } else if(t == num) {
        return 0;
    } else {
        return 1;
    }
}

LL binarySearch(char n2[], LL left, LL right, LL t) {   //二分求解N2的進制
    LL mid;
    while(left <= right) {
        mid = (left + right) / 2;
        int flag = cmp(n2, mid, t);
        if(flag == 0) {
            return mid;
        } else if(flag == -1) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    return -1;      //解不存在
}

int findLargest(char n2[]) {    //尋找N2的最大數位
    int ans = -1;
    int len = strlen(n2);
    for(int i = 0; i < len; i++) {
        if(m[n2[i]] > ans) {
            ans = m[n2[i]];
        }
    }
    return ans + 1;     //最大數位為ans，說明進制底線為ans+1
}

int main() {
    char n1[20], n2[20], temp[20];
    int tag, radix;
    init();
    scanf("%s %s %d %d", n1, n2, &tag, &radix);
    if(tag == 2) {
        swap(n1, n2);
    }
    LL t = convertTo10(n1, radix, inf);
    LL low = findLargest(n2);   //找到N2的最大數位，當成二分下界
    LL high = max(low, t) + 1;  //上界
    LL ans = binarySearch(n2, low, high, t);    //二分
    if(ans == -1) {
        printf("Impossible\n");
    } else {
        printf("%lld\n", ans);
    }
    return 0;
}