PAT A-1010 Radix 题解

题目地址: PAT A-1010 Radix.

若 tag == 2, 交换 N1 和 N2, 则题目等价于给定 $N_1$, $N_2$, $r$ 及如下方程, 求解满足条件的最小 $x$:

和其他的进制转换题一样, 核心都是将不同进制下的数字转换为十进制做对比. 但由于题目表述不严谨加之没有给出数据范围, 所以有很多坑需要注意.

将 $N_1$ 与 $N_2$ 的第 $i$ 位分别用 $a_i$ 与 $b_i$ 表示, 可以将这两个数转写为:

求解等式的过程就是在解一个一元多次方程, 若线性遍历 $x$ 的取值范围则时间复杂度为 $O(N)$. 但题目虽然限制了字符集取值范围是 0-9, a-z, 但并没有说进制最大取值为 $36$, 理论上可以无限大, 故这样的时间复杂度是不可接受的.

由于随着 $x$ 的增长, $(N_2)_x$ 单调递增. 从一个单调递增的数列中找出特定值, 符合二分结构, 所以采用二分答案的方法, 对所求值 $x$ 的取值范围进行二分查找.

要使得 $(N_2)_x$ 为一个合法数字, 其每一个字符必须在 $x$ 进制的合法字符集中. 如 $(16ab)_{12}$ 在 $12$ 进制以下非法. 由此我们可以求出 $x$ 的最小取值 base_lo:

#include <unordered_map>

const std::unordered_map<char, int> DIGITS = []() {
    std::unordered_map<char, int> m;
    for (int i = 0; i < 10; ++i)
        m['0' + i] = i;
    for (int i = 0; i < 26; ++i)
        m['a' + i] = 10 + i;
    return m;
}();

#include <string>
#include <iostream>
#include <algorithm>

std::string n2;
std::cin >> n2;
long long base_lo = DIGITS.at(*std::max_element(n2.begin(), n2.end())) + 1;

在这里, 我们首先创建了一个字符到十进制数字的对应表 DIGITS, 然后以字符串形式存储 n2, 找出最大的字符, 其对应十进制值加一即为 $x$ 的最小取值.

接下来确定 $x$ 的最大取值. 观察到当 $x \gt (N_1)_r$ 时, $\forall j \gt 0, x^j \gt (N_1)_r$.

此时若 $b_j b_{j-1} ... b_2 b_1 \ne 0$, 则必有 $(N_2)_x = b_j x^j + b_{j-1} x^{j-1} + ... + b_1 x + b_0 > (N_1)_r$;
若 $b_j b_{j-1} ... b_2 b_1 = 0$, 则 $(N_2)_x = (b_0)_x = (b_0)_{b_0 + 1}$, 此时 $x$ 取值无意义, 都等效于 $x = b_0 + 1 = x_{min}$.

由此可确定 $x$ 的最大取值 $x_{max} = max[(N_1)_r, x_{min}]$. 对应代码:

auto str_to_int_of_base(const std::string s) {
    return [=](const int base) {
        std::string n = s;
        long long n_10 = 0;
        long long multitude = 1;
        while (n.size()) {
            n_10 += DIGITS.at(n.back()) * multitude;
            n.pop_back();
            multitude *= base;
        }
        return n_10;
    };
}
                

std::string n1;
int radix;
std::cin >> n1 >> radix;
const long long n1_10 = str_to_int_of_base(n1)(radix);

#include <cstdlib>

long long base_hi = std::max(n1_10, base_lo) + 1;

这里先使用 long long str_to_int_of_base(const std::string s)(const int base) 函数将字符串 n1 转化为十进制, 然后与 base_lo 对比. 此处的 + 1 是为了满足程序设计中左闭右开的习惯, 将 base_hi 作为无法达到的上界.

经典的二分查找. 这里最大的坑就是当 $x$ 很大时, $(N_2)_x$ 可能超越 LONG_LONG_MAX 变成负数, 需要加条件判断. 理论上说, $x$ 取值无限大, 故可能存在 $x_1 > x_2$ 使得 $(N_2)_{x_1} \equiv (N_2)_{x_2} \mod{(ULONG\_LONG\_MAX)}$.

虽然题目说明了在存在多个解的情况下, 只需要输出最小的那个, 暗示我们不用考虑高精度问题, 但没有明说 $(N_1)_r$ 是否在 long long 范围内, 仍会令人感到困惑.

const auto n2_of = str_to_int_of_base(n2);

bool found = false;
long long base_mid;
while (base_lo < base_hi) {
    base_mid = (base_lo + base_hi) / 2;
    long long n2_10_of_base_mid = n2_of(base_mid);
    if (n2_10_of_base_mid > n1_10 || n2_10_of_base_mid < 0)
        base_hi = base_mid;
    else if (n2_10_of_base_mid < n1_10)
        base_lo = base_mid + 1;
    else {
        std::cout << base_mid << std::endl;
        found = true;
        break;
    }
}

if (!found)
    std::cout << "Impossible" << std::endl;

时间复杂度: $O(\log{(N_1)_r})$
空间复杂度: $O(1)$