确定进制

题目描述

给定三个数字串 $p,q,r$ （每位都是数字， $1\le p,q,r\le 10^6$ ），求最小的进制 $B$ （ $2\le B\le 40$ ），使得把它们按 $B$ 进制解释后满足 $p\times q=r$ ；不存在则输出 $0$ 。

思路

从小到大枚举 $B$ ，检查每位数字是否小于 $B$ ，再用 Horner 展开把三串转成十进制，若 $p\times q=r$ 则 $B$ 为答案。枚举范围仅 39 个，直接暴力即可。

参考代码

Python 版：

python

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#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-09-30 09:24
# update_at: 2026-09-30 09:24

import sys

B_MAX = 40  # 进制 B 的枚举上界（含）


def to_base(s: str, base: int) -> int:
    """把数字串 s 当作 base 进制转成十进制；出现非法数字则返回 -1。"""
    value = 0
    for ch in s:
        digit = ord(ch) - ord('0')
        if digit >= base:  # 某一位数字超出进制允许范围，非法
            return -1
        value = value * base + digit
    return value


def solve() -> None:
    p, q, r = sys.stdin.read().split()

    # 从小到大枚举进制，第一个满足 p*q=r 的就是答案
    ans = next(
        (
            base
            for base in range(2, B_MAX + 1)
            if (x := to_base(p, base)) > 0
            and x * to_base(q, base) == to_base(r, base)
        ),
        0,  # 没有任何进制合法
    )
    print(ans)


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

cpp

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/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-05 23:14
 * update_at: 2026-10-05 23:14
 */
#include <iostream>
#include <string>
using namespace std;

typedef long long ll;

string p, q, r;

// 把数字串 s 当作 base 进制转成十进制；出现非法数字则返回 -1
ll to_base(const string &s, int base) {
    ll value = 0;
    for (char ch : s) {
        int digit = ch - '0';
        if (digit >= base) return -1; // 某一位数字超出进制允许范围，非法
        value = value * base + digit;
    }
    return value;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> p >> q >> r;
    for (int base = 2; base <= 40; ++base) {
        ll pv = to_base(p, base);
        ll qv = to_base(q, base);
        ll rv = to_base(r, base);
        if (pv >= 0 && qv >= 0 && rv >= 0 && pv * qv == rv) {
            cout << base << '\n';
            return 0;
        }
    }
    cout << 0 << '\n';
    return 0;
}

目录

题目描述

思路

参考代码