自动搬运

查看原文

来自洛谷，原作者为

	红黑树 https://rbtr.ee

搬运于2025-08-24 21:07:41，当前版本为作者最后更新于2021-09-03 01:14:19，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

做法：

既然要找最小满足要求的进制，那就从可能的最小的进制开始枚举 确定最小可能进制的代码如下

inline int Min(string p, string q, string r) {
    char MIN = *max_element(p.begin(), p.end());
    MIN = max(MIN, *max_element(q.begin(), q.end()));
    MIN = max(MIN, *max_element(r.begin(), r.end()));
    // max_element() 返回给定区间中最大的元素
    // 到此为止，MIN 中存的东西就是 p, q, r 中 ASCII 码最大的字母了
    return MIN - '0' + 1; // 为什么是 MIN - '0' + 1 呢，比如 2 进制中不可能出现 2，3 进制中不可能出现 3
}

那么如何判断当前进制是否符合要求呢？ 我的做法是将两个 $B$ 进制数转化为 $10$ 进制后相乘，得到的结果再转换成 $B$ 进制，与 $r$ 判断是否相等，其他进制乘法要重新写，有点麻烦

代码如下

inline int B_to(int B, string n) { // n 从 B 进制转换到 10 进制
    int num = 0; // 初始化答案为 0
    reverse(n.begin(), n.end()); // 由于我们从 n 的开始枚举到 n 的末尾，需要把数组翻转一下，另一种解决方案是从末尾开始往头枚举
    for (int i = 0; i < n.size(); i++) {
        if (n[i] >= '0' && n[i] <= '9') // 如果当前这一位存的是 0 到 9
            num += pow(B, i) * (n[i] - '0'); // 位权 * 值
        else // 是字母
            num += pow(B, i) * (n[i] - 'A' - 10); // 位权 * 值
    }
    return num; // 返回计算好的答案
}

inline string TO_Be(int B, int n) {
    string num = ""; // 初始化 num 为空
    for (; n; n /= B) // 除以 B 相当于是在 B 进制中右移一位
        num.push_back(n % B); // % B 相当于取出 B 进制下的最低位
    reverse(num.begin(), num.end());
    for (auto& i : num) { // 扫描 num 数组
        (i >= 0 && i <= 9) ? i += '0' : i += 'A' - 10; // 如果 i 不是数字，要转换成字母
    }
    return num; // 返回计算好的答案
}

那么代码就出来了

#include <iostream> // 提供 cin 和 cout
#include <algorithm> // 提供 reverse 函数 和 max_element 函数
#include <string> // string 类
#include <cmath> // pow 函数
// 此题需要开 long long 不然 90 分

using namespace std;

inline string TO_Be(int B, long long n) {
    string num = "";
    for (; n; n /= B)
        num.push_back(n % B);
    reverse(num.begin(), num.end());
    for (auto& i : num) {
        (i >= 0 && i <= 9) ? i += '0' : i += 'A' - 10;
    }
    return num;
}

inline long long B_to(int B, string n) {
    long long num = 0;
    reverse(n.begin(), n.end());
    for (int i = 0; i < n.size(); i++) {
        if (n[i] >= '0' && n[i] <= '9')
            num += pow(B, i) * (n[i] - '0');
        else
            num += pow(B, i) * (n[i] - 'A' - 10);
    }
    return num;
}

inline int Min(string p, string q, string r) {
    char MIN = *max_element(p.begin(), p.end());
    MIN = max(MIN, *max_element(q.begin(), q.end()));
    MIN = max(MIN, *max_element(r.begin(), r.end()));
    return MIN - '0' + 1;
}

int main() {
    string q, p, r;
    cin >> p >> q >> r;
    for (int B = Min(p, q, r); B < 17; B++) {
        long long pmq = B_to(B, p) * B_to(B, q); // 计算 10 进制乘积
        if (TO_Be(B, pmq) == r) { // 把计算好的乘积转换成 B 进制，然后判等
            cout << B; // 符合条件就输出 B
            return 0; // 结束程序
        }
    }
    cout << 0; // 如果所有进制都不行，按照题目要求输出 0
    return 0;
}