PAT-A 1010 Radix (25)

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.

Problem: PAT-A 1010 Radix

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

1

6 110 1 10

Sample Output 1

1

2

Sample Input 2

1

1 ab 1 2

Sample Output 2

1

Impossible

Analysis

  给两个数，已知其中一个数的基数，判断另一个数是否存在基数使两个数相等，求出该基数，不存在则输出 Impossible。从题意来看就是普通的进制转换，先求出已知基数的数的 10 进制，再求出另一个数在不同基数下转为 10 进制的值，比较两数大小，如果相等则当前基数为所求解。但是测试点很恐怖，参考了大佬的代码才全过。遇到以下坑：

• 题目未说明 基数取值范围。实际下限大于未知基数的数中的任何一个数字，上限为已知基数的数，并不是简单的数字 + 字母的 [2, 35]。
• 题目只说明了数最大有 10 位，所以 int 显然不够存了，而且如果基数比较大，那么 long long 也不够存。根据前辈们的踩坑经历，幸好测试用例中所有数据都在 long long 范围内，不然就太折腾了。
• 由于基数可能非常大，从小到大一个个遍历会有一个测试点过不去，因此搜索基数的时候采用 二分查找，使用的上限和下限也就是基数的取值范围。
• 二分查找的过程中会出现 long long 溢出 导致返回值为负数，查找时要增加判断。

Code

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

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

// 字符串转 10 进制
ll str_to_dec(string str, ll radix) {
    ll res = 0;
    int len = str.size();
    for (int i = 0; i < len; i++) {
        int tmp = (isdigit(str[i]) ? str[i] - '0' : str[i] - 'a' + 10);
        res += tmp * pow(radix, len - i - 1);
    }
    return res;
}

// 获取基数
ll get_radix(string str, ll num) {  // num 为已知数的 10 进制
    ll radix = 0;

    // 计算基数范围
    char maxC = *max_element(str.begin(), str.end()); // 找到最大字符
    ll lo = (isdigit(maxC) ? maxC - '0' : maxC - 'a' + 10) + 1;
    ll hi = max(lo, num);

    // 使用二分查找计算基数
    while (lo <= hi) {
        ll mid = (lo + hi) / 2;
        ll tmp = str_to_dec(str, mid);
        if (tmp > num || tmp < 0) {  // 比已知数大或向上溢出
            hi = mid - 1;
        } else if (tmp < num) {  // 比已知数小
            lo = mid + 1;
        } else {
            radix = mid;
            break;
        }
    }
    return radix;
}

int main() {
    string N1, N2;
    int tag, radix;
    cin >> N1 >> N2 >> tag >> radix;
    ll num = (tag & 1) ? str_to_dec(N1, radix) : str_to_dec(N2, radix);
    ll ans = (tag & 1) ? get_radix(N2, num) : get_radix(N1, num);
    if (ans) {
        cout << ans << endl;
    } else {
        cout << "Impossible" << endl;
    }
}

Tsukkomi

  测试点太恶心（个人太菜），题目表述也不清（还是个人太菜）。折腾一下午，看着 20 个测试点的结果不断变换，始终有几个点过不去，心态爆炸。嫖完大佬的思路拐回来写，顿时觉得也没什么难度了，主要还是菜。