PAT Advanced 1010. Radix (25) (C语言实现)

我的PAT系列文章更新重心已移至Github，欢迎来看PAT题解的小伙伴请到Github Pages浏览最新内容。此处文章目前已更新至与Github Pages同步。欢迎star我的repo。

题目

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:

Sample Input 2:

1 ab 1 2

Sample Output 2:

Impossible

思路

一开始以为数字是0-9a-z，那进制最多就是36，结果一小半都错。看了一下别人的方法，才知道进制并没有任何限制。

几个要点：

用二分查找法（binary search）。因为radix范围是2～LLONG_MAX，逐一遍历肯定是算到地老天荒的。（LLONG_MAX是long long能存储的最大值，定义在头文件limits.h中）
运算中过大的数的处理。如果预计计算结果会大于long long int范围，就返回一个代表溢出的结果（如-1）。
关于“If the solution is not unique, output the smallest possible radix.”，这只能发生在未知进制的数只有一位的情况下，它在任何进制下的值都是一样的，这样如果它等于已知数，最小可能进制就是这个数加1，否则就无解。

当然我在处理溢出的时候并没有像大多数人（我也不知道是不是大多数，因为10篇博客有8篇都是雷同的）将结果和已知数对比，而是和LLONG_MAX对比，当然不能直接将结果算出来了，具体看我的代码base10函数。
另外由于我是在LLONG_MAX以内查找，因此二分查找第一次求平均时就是LLONG_MAX加一个数除以二，这里就溢出了，所以这里也做了防溢出。具体在binsearch函数。

P.S. 其实这道题用long long类型存储在严格的分析下也是不够的，比如说最大的情况（worst scenario）：所给的数是zzzzzzzzzz，它的进制是2^31-1（INT_MAX，既然没限制，那么这就是最小合理上限），另一个数是10，那后者的进制可以是前者的10进制的值，约是：3.5*10⁸⁵，远远大于C语言内置数据类型的容量。我也想过实现下满足这样苛刻要求的方法，用多个int表示一个超大的数，但是运算上比较麻烦，没个200行写不下，所以就暂时按照大多数人的思路写了，反正能AC╭(╯^╰)╮

代码

最新代码@github，欢迎交流

#include <ctype.h>
#include <stdio.h>
#include <limits.h>
#include <string.h>

#define OVERFLOW -1
#define NOTFOUNT -1
#define CBASE10(C) ((C) >= '0' && (C) <= '9' ? (C) - '0' : (C) - 'a' + 10)

/* Calculate decimal value of a text-form number s under a radix */
long long base10(char *s, long long radix)
{
    long long n, sum;
    for(sum = 0; *s; s++)
    {
        n = CBASE10(*s);
        if((LLONG_MAX - n) / radix < sum) /* overflow */
            return OVERFLOW;
        sum = sum * radix + n;
    }
    return sum;
}

/* Find the smallest possible radix of a numbers */
int minradix(char *s)
{   /* Simply the largest digit in the number plus 1 */
    char r;
    for(r = '0'; *s; s++)
        if(*s > r)
            r = *s;
    return CBASE10(r) + 1;
}

/* Use binary search to locate radix of s which makes it equals n */
long long binsearch(char *s, long long n, long long rmin, long long rmax)
{
    long long r, m;
    while(rmax >= rmin)
    {
        r = rmin + (rmax - rmin) / 2; /* avoid (rmin + rmax) overflow */
        if((m = base10(s, r)) > n || m == OVERFLOW)
            rmax = r - 1;
        else if(m < n)
            rmin = r + 1;
        else
            return r;
    }
    return NOTFOUNT;
}

int main()
{
    int tag, radix;
    long long N1, rmin, rmax, r;
    char buf1[11], buf2[11], *S1, *S2;

    /* Make S1 point to the number with known radix, S2 to the other */
    scanf("%s %s %d %d", buf1, buf2, &tag, &radix);
    if(tag == 1) S1 = buf1, S2 = buf2;
    if(tag == 2) S1 = buf2, S2 = buf1;

    N1 = base10(S1, radix);     /* Corresponding decimal of S1 */
    rmin = minradix(S2);        /* Smallest possible radix of S2 */
    rmax = LLONG_MAX;           /* Largest possible radix of S2 */
    if(strlen(S2) == 1) /* If so, N2 will be same value under any radix */
    {                           /* rmin - 1 (naturally equals N2) equals N1 */
        if(N1 == rmin - 1)      printf("%lld", rmin);
        else                    printf("Impossible");
    }
    else                /* Binary search to find the radix of N2 */
    {
        r = binsearch(S2, N1, rmin, rmax);
        if(r != NOTFOUNT)       printf("%lld", r);
        else                    printf("Impossible");
    }

    return 0;
}