双重回文数

题目描述

若一个数从左往右读与从右往左读相同，且首尾非零，则称它为回文数。有些数在十进制下不是回文，在其它进制下却是回文。

给定 $N\ (1 \le N \le 15)$ 和 $S\ (0 < S < 10000)$ ，找出大于 $S$ 、且在二进制到十进制中至少有两种进制下为回文数的前 $N$ 个整数，按升序每行输出一个。

样例：输入 3 25，输出 26、27、28。

思路

从 $S+1$ 开始升序枚举每个整数，对每个候选数在 $2\sim10$ 进制分别用短除法取余得到数码串，再判断是否为回文；回文进制数达到 2 个即输出，累计输出 $N$ 个后停止。

参考代码

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
42
43
44
45#!/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-10-01 02:42
# update_at: 2026-10-01 02:42

import sys
from collections.abc import Iterator
from itertools import count, islice

BASE_MAX = 10  # 题面进制范围：二进制到十进制
NEED = 2       # “两种以上进制”即至少 2 种进制下回文


def is_palindrome(value: int, base: int) -> bool:
    """value 在 base 进制下的数码序列是否左右对称。

    除到商为 0 为止，得到的余数顺序就是低位到高位；首位数码一定非零，
    所以比较数码序列与它的逆序即可，不必再额外判前导零。
    """
    digits: list[int] = []
    while value:
        digits.append(value % base)
        value //= base
    return digits == digits[::-1]


def palindrome_bases(value: int) -> int:
    """value 在 2~10 进制中成为回文数的进制个数。"""
    return sum(is_palindrome(value, base) for base in range(2, BASE_MAX + 1))


def dual_palindromes(n: int, s: int) -> Iterator[int]:
    """按从小到大顺序产出前 n 个“大于 s 的双重回文数”。"""
    return islice((v for v in count(s + 1) if palindrome_bases(v) >= NEED), n)  # 找到 n 个即停


def solve() -> None:
    n, s = map(int, sys.stdin.buffer.read().split())
    print(*dual_palindromes(n, s), sep="\n")


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
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57/**
 * 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-06 09:25
 * update_at: 2026-10-06 09:25
 */

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

typedef long long ll;

ll n, s;

// 判断 x 在 base 进制下是否为回文
bool is_palindrome(ll x, ll base) {
    ll digits[64]; // 低位在前保存各进制数码
    ll len = 0;
    while (x > 0) {
        digits[len++] = x % base;
        x /= base;
    }
    for (ll i = 0; i < len / 2; i++) {
        if (digits[i] != digits[len - 1 - i]) {
            return false;
        }
    }
    return true;
}

// 统计 x 在 2~10 进制中回文的进制个数
ll count_palindrome(ll x) {
    ll cnt = 0;
    for (ll base = 2; base <= 10; base++) {
        if (is_palindrome(x, base)) {
            cnt++;
        }
    }
    return cnt;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n >> s;
    ll found = 0;
    ll x = s + 1;
    while (found < n) {
        if (count_palindrome(x) >= 2) {
            cout << x << "\n";
            found++;
        }
        x++;
    }
    return 0;
}

目录

题目描述

思路

参考代码