原题目

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₁ and N₂, 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

题目大意

给一对正整数，例如6和110，等式 6 = 110成立的条件是6是一个十进制数字且110是一个二进制数字。
输入一行4个正整数，N1和N2是两个不多于10个数字的数，其中一个数字从集合{0-9, a-z}中取且数值小于它的进制。输入的radix表示第tag个数的进制，tag取1或2。输出未知进制数能满足等式 N1 = N2时最小的进制，若不能满足等式则输出Impossible。

题解

不愧是通过率只有0.11的题，实在是太多坑了。
首先10位的数字不能直接用int进行存储和读入。一开始我是自己写了大整数模板来进行数据存储及进制转换，但是因为太麻烦就放弃了懒得写除法。看过其他人写的题解后知道了用long long可以直接过，但是也存在溢出的问题，在进行进制转换时如果long long溢出为负需及时舍去。
然后就是题目中说的每一位数字都从{0-9, a-z}中取，即每一位数字的大小都不超过35，并不代表radix最高只能取36，相反，进制的数值可以在long long的范围内取，只要不超过已知进制数的十进制数值加1。
最后，如果选用暴力搜索的办法，从未知进制数的最大数字加1一直搜索到已知进制数的数值加1，在测试点7会直接超时用大整数做的时候直接内存超限了。因此只能选择二分法，选好上下界，迭代出结果。注意要求输出满足条件的最小进制不过好像不写那段代码也能过。

C语言代码如下：

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define max(a, b) (a) > (b) ? (a) : (b)

long long string_2_long(char *num, long long radix){
    long long ret = 0;
    long long base = 1;
    for(int i = strlen(num) - 1;i >= 0;--i){
        int time = num[i] > '9' ? num[i] - 'a' + 10 : num[i] - '0';
        if(ret > ret + time * base) return -1;
        ret += time * base;
        base *= radix;
    }
    return ret;
}

int main(){
    char num1[12], num2[12];
    int tag;
    long long radix;
    char maxx = 0;
    scanf("%s%s%d %lld", num1, num2, &tag, &radix);
    long long src, dest;
    if(tag == 1){
        src = string_2_long(num1, radix);
        memcpy(num1, num2, 12); //将num1作为待确定的字符串
    }
    else{
        src = string_2_long(num2, radix);
    }
    for(int i = 0;i < strlen(num1);++i){
        maxx = max(num1[i], maxx);
    }
    long long low = (maxx > '9' ? maxx - 'a' + 10 : maxx - '0') + 1;
    long long high = max(src + 1, low);
    if(src < string_2_long(num1, low)){
        printf("Impossible\n");
        return 0;
    }
    while(high >= low){
        long long mid = (high + low) / 2;
        long long tmp = string_2_long(num1, mid);
        if(src == tmp){
            mid--;
            while (mid >= low){
                if(string_2_long(num1, mid) == src){
                    mid--;
                }
                else{
                    break;
                }   
            }   
            printf("%d\n", mid + 1);
            return 0;
        }
        else if(src < tmp || tmp < 0){
            high = mid - 1;
        }
        else{
            low = mid + 1;
        }
    }
    printf("Impossible\n");
    return 0;
}