我的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 and
, 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
思路
一开始以为数字是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，它的进制是231-1（INT_MAX，既然没限制，那么这就是最小合理上限），另一个数是10，那后者的进制可以是前者的10进制的值，约是：3.5*1085，远远大于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;
}
