usaco-1.2.4 回文平方数

题目描述

回文数是从左向右读和从右向左读都一样的数，例如 12321。给定一个进制 $B$ （ $2 \leqslant B \leqslant 20$ ），输出所有大于等于 1 且小于等于 300、并且它的平方用 $B$ 进制表示时是回文数的数，用 A、B……表示 10、11 等数码。

输入样例（B = 10），输出样例（共 12 行，每行形如 x repr_B(x^2)，此处为节省篇幅合并为一行展示，实际输出每对占一行）：

text

1
21 1 / 2 4 / 3 9 / 11 121 / 22 484 / 26 676
101 10201 / 111 12321 / 121 14641 / 202 40804 / 212 44944 / 264 69696

思路

按定义枚举 $x = 1 \sim 300$ ，用短除法把 $x^2$ 转成 $B$ 进制串（余数从低位到高位产生，前置拼接保证高位在前， $10 \sim 19$ 查表映射为 A ~ J），再判断该串正读反读是否相同。是回文就同时把 $x$ 和 $x^2$ 转成 $B$ 进制输出一行；按 $x$ 升序枚举，结果天然有序。注意回文条件加在平方上而不是 $x$ 上（如 $B=10$ 时 26 不是回文数，但 $26^2=676$ 是）。

参考代码

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#!/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:40
# update_at: 2026-10-01 02:40

import sys
from collections.abc import Iterator

MAX_N = 300  # 题面要求枚举的范围 [1, 300]，与进制 B 无关
DIGITS = "0123456789ABCDEFGHIJ"  # 数码表：下标即权值，10~19 用 A~J 表示


def to_base(value: int, base: int) -> str:
    """把十进制正整数写成 base 进制串（最高位在前）。"""
    digits = ""
    while value:
        digits = DIGITS[value % base] + digits  # 余数从低位到高位产生，故前置拼接
        value //= base
    return digits


def palindrome_squares(base: int) -> Iterator[tuple[int, str]]:
    """产出 [1, MAX_N] 内所有「平方是回文数」的 (原数, 平方的 base 进制串)。"""
    for x in range(1, MAX_N + 1):
        square = to_base(x * x, base)
        if square == square[::-1]:  # 反转后相同即为回文
            yield x, square


def solve() -> None:
    base = int(sys.stdin.read())
    out = [f"{to_base(x, base)} {square}" for x, square in palindrome_squares(base)]
    print("\n".join(out))


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
58
59/**
 * 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 <cstdio>
#include <string>

typedef long long ll;

const ll MAX_N = 300; // 题面要求的枚举上界：1 <= x <= 300

ll base;      // 输入的进制 B（2~20）
char buf[50]; // 临时存放一条 B 进制串，用于反转比较

// 把十进制非负整数 value 写成 base 进制串（最高位在前）。
// 10~19 的数码依次用 'A'~'J' 表示。
std::string to_base(ll value) {
    std::string digits = "";
    if (value == 0)
        return "0";
    while (value) {
        int r = value % base; // 余数即当前最低位
        char c;
        if (r < 10)
            c = '0' + r;
        else
            c = 'A' + r - 10; // 数码 10~19 记为 A~J
        digits = c + digits;  // 余数从低位到高位产生，故前置拼接保证高位在前
        value /= base;
    }
    return digits;
}

// 判断字符串 s 是否为回文串。
bool is_palindrome(const std::string &s) {
    ll i = 0, j = s.size() - 1;
    while (i < j) {
        if (s[i] != s[j])
            return false;
        i++;
        j--;
    }
    return true;
}

int main() {
    scanf("%lld", &base);
    // 按 x 升序枚举，输出天然有序；回文条件加在平方上而不是 x 上
    for (ll x = 1; x <= MAX_N; x++) {
        std::string sq = to_base(x * x);
        if (is_palindrome(sq))
            printf("%s %s\n", to_base(x).c_str(), sq.c_str());
    }
    return 0;
}

usaco-1.2.4 回文平方数

目录

题目描述

思路

参考代码