题解 | 回文数

#include <stdio.h>
#include <string.h>
#include <ctype.h>

// 将字符转换为数值，支持0-9和A-F
int charToInt(char c) {
    if (c >= '0' && c <= '9') return c - '0';
    return c - 'A' + 10;
}

// 将数值转换为字符
char intToChar(int x) {
    if (x < 10) return '0' + x;
    return 'A' + (x - 10);
}

// 判断数组a[0..len-1]（低位在前）是否为回文
int isPalindrome(int a[], int len) {
    for (int i = 0; i < len / 2; i++) {
        if (a[i] != a[len - 1 - i]) return 0;
    }
    return 1;
}

// N进制加法：a + reverse(a) 结果存入新数组，返回新长度
int addReverse(int a[], int len, int N, int res[]) {
    // 先得到a的逆序b
    int b[1000];
    for (int i = 0; i < len; i++) {
        b[i] = a[len - 1 - i];
    }
    // 相加
    int carry = 0;
    int maxLen = len; // 结果长度至少为len
    for (int i = 0; i < len; i++) {
        int sum = a[i] + b[i] + carry;
        res[i] = sum % N;
        carry = sum / N;
    }
    if (carry) {
        res[len] = carry;
        maxLen = len + 1;
    } else {
        maxLen = len;
    }
    return maxLen;
}

int main() {
    int N;
    char M[1000];
    scanf("%d", &N);
    scanf("%s", M);

    // 将M转换为数字数组，低位在前
    int len = strlen(M);
    int a[1000];
    for (int i = 0; i < len; i++) {
        a[i] = charToInt(M[len - 1 - i]); // 低位在前
    }

    int step = 0;
    while (step <= 30) {
        if (isPalindrome(a, len)) {
            printf("STEP=%d\n", step);
            return 0;
        }
        if (step == 30) break; // 已经30步未成功，再一步会超过30
        int res[1000];
        len = addReverse(a, len, N, res);
        // 将结果复制回a
        for (int i = 0; i < len; i++) a[i] = res[i];
        step++;
    }
    printf("Impossible!\n");
    return 0;
}