题目

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:

1

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:

1

6 110 1 10

Sample Output 1:

1

2

Sample Input 2:

1

1 ab 1 2

Sample Output 2:

1

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^85^，远远大于C语言内置数据类型的容量。我也想过实现下满足这样苛刻要求的方法，用多个int表示一个超大的数，但是运算上比较麻烦，没个200行写不下，所以就暂时按照大多数人的思路写了，反正能AC╭(╯^╰)╮

代码

Github最新代码，欢迎交流

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75

#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 */
		if (N1 == rmin - 1)     /* rmin - 1 (naturally equals N2) equals N1 */
			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;
}