【例1.6】回文数(Noip1999)

题目描述

若一个数（首位不为零）从左向右读与从右向左读都一样，称之为回文数。给定进制 $N$ （ $2 < N \leqslant 10$ 或 $N = 16$ ）和一个 $N$ 进制数 $M$ （数码用 0–9、A–F 表示），定义一步操作为：把 $M$ 与"它的数码反转得到的数"做一次 $N$ 进制加法。求最少几步能得到回文数；若 $30$ 步以内（含 $30$ 步）不能得到，输出 Impossible。若 $M$ 本身就是回文数，答案为 $0$ 。例如 10 进制 $87$ ： $87+78=165 \to 165+561=726 \to 726+627=1353 \to 1353+3531=4884$ ，共 $4$ 步。

输入：一行，进制 $N$ 和 $N$ 进制数 $M$ 。输出：最少步数，或 Impossible。样例：输入 9 87，输出 6。

思路

把 $M$ 按字符面值直接读进低位在前的数码数组（不要转整数：数据里存在数码值 $\geqslant N$ 的输入，如 2 37，转整数语义就错了），然后反复做「 $a \leftarrow a + \operatorname{reverse}(a)$ 」的 $N$ 进制加法：逐位求和后从低位到高位每位做一次除 $N$ 取余，最高位进位直接追加。第 $0$ 步先判回文（覆盖初始即回文的情形），之后每做一步判一次， $30$ 步用尽仍未回文就输出 Impossible。

参考代码

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
46#!/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-07-05 22:10
# update_at: 2026-07-05 22:10

import sys

DIGITS = '0123456789ABCDEF'   # 值 → N 进制字符，N 最大 16，恰好够用
VALUES = {c: i for i, c in enumerate(DIGITS)}          # 大写字母的值
VALUES |= {c.lower(): i for i, c in enumerate(DIGITS) if c.isalpha()}  # 补小写


def add_reverse(a: list[int], base: int) -> list[int]:
    """返回 a + reverse(a) 在 base 进制下的数码数组（低位在前，可能多一位）。"""
    s = [x + y for x, y in zip(a, a[::-1])]
    for i in range(len(s)):
        carry, s[i] = divmod(s[i], base)
        if carry:                                        # 进位累加到更高位
            if i + 1 < len(s):
                s[i + 1] += carry
            else:
                s.append(carry)
    return s


def solve() -> None:
    base_s, m = sys.stdin.read().split()
    base = int(base_s)                                  # 进制 N（2 < N <= 10 或 N = 16）
    a = [VALUES[c] for c in m][::-1]                    # 数码数组，低位在前

    for step in range(31):                              # 第 0 步先判初始是否回文
        is_palindrome = a == a[::-1]
        if is_palindrome:
            print(step)
            return
        if step == 30:                                  # 30 步用尽仍未回文
            break
        a = add_reverse(a, base)                        # 一次 N 进制加法

    print('Impossible')


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
60
61
62
63
64
65
66
67
68
69
70
71/**
 * 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 09:01
 * update_at: 2026-10-05 09:07
 */
#include <cstdio>
#include <cstring>

typedef long long ll;

const int MAXL = 1005;

int base;        // 进制 N（2 < N <= 10 或 N = 16）
int len;         // 当前数码长度
int a[MAXL];     // 数码数组，低位在前

// 字符转面值：0-9、A-F（含小写）
int char_value(char c) {
    if (c >= '0' && c <= '9') return c - '0';
    if (c >= 'A' && c <= 'F') return c - 'A' + 10;
    if (c >= 'a' && c <= 'f') return c - 'a' + 10;
    return -1;
}

// 判断当前数码序列（低位在前）是否回文
bool is_palindrome() {
    for (int i = 0, j = len - 1; i < j; i++, j--)
        if (a[i] != a[j]) return false;
    return true;
}

// 一次 N 进制加法：a = a + reverse(a)
// 与评测机（原 main.py，已 AC）语义一致：只对原有 len 位做 "除 base 取余" 归化，
// 最高位溢出的进位直接追加落地，不再继续归约（数据可能有越界数码）
void add_reverse() {
    int s[MAXL + 5];  // 逐位求和的结果，s[i] = a[i] + a[len-1-i]
    int n = len;
    int bound = n;    // 只归化原有 len 位，与 Python 的 range(len(s)) 一致
    for (int i = 0; i < len; i++) s[i] = a[i] + a[len - 1 - i];
    for (int i = 0; i < bound; i++) {      // 上界固定为旧 len，新追加的最高位不再归约
        int carry = s[i] / base;
        s[i] %= base;
        if (carry > 0) {
            if (i + 1 < n) s[i + 1] += carry;
            else { s[n] = carry; n++; }    // 最高位进位直接落地
        }
    }
    len = n;
    for (int i = 0; i < len; i++) a[i] = s[i];
}

int main() {
    char str[MAXL];
    scanf("%d %s", &base, str);
    len = strlen(str);
    for (int i = 0; i < len; i++) a[i] = char_value(str[len - 1 - i]); // 低位在前

    // 第 0 步先判初始是否回文，之后最多做 30 次加法
    for (int step = 0; step <= 30; step++) {
        if (is_palindrome()) {
            printf("%d\n", step);
            return 0;
        }
        if (step == 30) break;
        add_reverse();
    }
    printf("Impossible\n");
    return 0;
}