【PAT甲级】1010 Radix

✍个人博客：https://blog.csdn.net/Newin2020?spm=1011.2415.3001.5343
📚专栏地址：PAT题解集合
📝原题地址：题目详情 - 1010 Radix (pintia.cn)
🔑中文翻译：进制
📣专栏定位：为想考甲级PAT的小伙伴整理常考算法题解，祝大家都能取得满分！
❤️如果有收获的话，欢迎点赞👍收藏📁，您的支持就是我创作的最大动力💪

1010 Radix

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 N1 and N2, 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
1

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
1

Sample Output 1:

2
1

Sample Input 2:

1 ab 1 2
1

Sample Output 2:

Impossible
1

题意

$N1$ 和 $N2$ 是两个不超过 $10$ 位的数字，radix 是其中一个数字的进制，如果 tag 为 $1$，则 radix 是 $N1$ 的进制，如果 tag 为 $2$，则 radix 是 $N2$ 的进制。

输出使得 $N1=N2$ 成立的另一个数字的进制数。

如果等式不可能成立，则输出 Impossible。

如果答案不唯一，则输出更小的进制数。

思路

这道题涉及到了秦九韶算法：

假设给定一个 d 进制 abc ，那么我要转化成十进制的公式为：$a\ast d^2+b\ast d^1+c$ ，放到循环中其实就是：

//假设n为字符串
long long res = 0;
for(auto x : n)
	res = res * d + x - '0';
1
2
3
4

具体步骤：

1. 先对输入的参数进行统一化操作，如果 $tag==2$ 就交换 $n1$ 和 $n2$ ，因为后续的操作都是对 $n1$ 取十进制 $target$ ，然后去找 $n2$ 的进制。
2. 由于 $n2$ 的进制是不固定的，它可以超过 $36$ 进制，所以有可能会非常大，例如 $n1$ 的十进制为 $88$ ，则 $n2$ 假如是 $10$ 则最大进制就可以取到 $88$ 。另外，当 $n2$ 位数为 $1$ 时，其进制数就至少要取到 $36$ ，因为当位数为 $1$ 时，其最大数为 $z$ ，也就是 $35$ ，我们即可取进制数最大 $36$ 。所以我们取上边界的公式为 $r=max(target,36ll)$ 。而下边界的 $l$ 则取 $n2$ 每一位中的最大值加 $1$ 。
3. 进行二分查找，如果当前进制下的 $n2$ 的十进制要大于等于 $n1$ 的十进制 $target$ ，则令 $r=mid$ ；反之，令 $l=mid+1$ 。
4. 输出最终结果。

代码

#include
using namespace std;

typedef long long LL;

//将字符转换成数字
int get(char c)
{
    if (c <= '9')  return c - '0';
    return c - 'a' + 10;
}

//获得十进制值
LL calc(string n, LL r)
{
    LL res = 0;
    for (auto c : n)
    {
        //double存的数字比long long更大
        //如果已经大于1e16则一定大于target，直接返回一个超大值即可
        if ((double)res * r + get(c) > 1e16) return 1e18;
        res = res * r + get(c);	//秦九韶算法
    }
    return res;
}

int main()
{
    string n1, n2;
    cin >> n1 >> n2;
    int tag, radix;
    cin >> tag >> radix;

    if (tag == 2)  swap(n1, n2);    //统一化处理
    LL target = calc(n1, radix);    //获得n1的十进制

    //获得二分的上边界和下边界
    LL l = 0, r = max(target, 36ll);
    for (auto c : n2)  l = max(l, (LL)get(c) + 1);

    //二分查找
    while (l < r)
    {
        LL mid = l + r >> 1;
        if (calc(n2, mid) >= target) r = mid;
        else    l = mid + 1;
    }

    if (calc(n2, r) == target) cout << r << endl;
    else puts("Impossible");

    return 0;
}
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