题解 | #[NOIP1999]回文数#

#include <stdio.h>
#include <stdlib.h>

/*
    十进制数转 数组N进制数
    N       进制
    D_num   十进制数
    M_L     数组N的长度(初始正常是0, 会改变)

    return 数组N进制数
*/
int* toN(int N, long long D_num, int *M_L) {
    int num[64] = {0};        // 存储伪N进制数
    while (D_num > 0) {
        int a = D_num % N;              // 得到余数
        D_num = (D_num - a ) / N ;     // 得到进位的数
        num[*M_L] = a;
        *M_L += 1;
    }

    // 伪N进制数->数组表示
    int* N_nums = calloc(*M_L + 1, sizeof(int));
    for (int i = 0; i < *M_L; i++) {
        N_nums[*M_L - i - 1] = num[i];
    }
    return N_nums;
}


/*
    
    数组N进制数 转十进制数
    N       进制
    M       数组-进制数(索引越小位数越大)
    len     数组长度

    return 十进制数
*/
int toTen(int N, int *M, int len) {
    int D_num = 0;
    for (int i = len; i > 0; i--) {
        int a = 1;
        for (int j = i - 1; j > 0; j--) {
            a *= N;
        }
        D_num += (M[len - i] * a);
    }
    return D_num;
}

// 获得进制数位数
void getNums(int num, int *numL) {
    int _num = num;
    while (_num > 0) {
        _num /= 10;
        *numL += 1;
    }
}

int main() {
    int N;
    scanf("%d", &N);
    if (N > 16) {
        return 0;
    }
    char none;
    scanf("%c", &none);
    char M[100] = {""};    // 100位数，故长度100;
    int m_i;
    while (scanf("%c", &M[m_i]) != EOF) {
        m_i++;
    }

    // 确定位数
    int M_L = 0;
    for (int i = 0; i < 100; i++) {
        if (M[i] == 10) break; // 换行结束
        M_L += 1;
    }

    long long D_num = 0;
    int* _M = calloc(M_L, sizeof(int));    // 数组进制数，方便后面反一下
    // 得到整数型数组进制数
    for (int i = 0; i < M_L; i++) {
        if (48 <= M[i] && M[i] <= 57) _M[i] = M[i] - 48;
        else if (65 <= M[i] && M[i] <= 70) _M[i] = M[i] - 55;
    }
    D_num = toTen(N, _M, M_L);

    int STEP = 0;
    int isMoreThirty = 0;
    while (1) {
        STEP++;
        /*相加操作*/
        // 反过来的进制数变十进制，然后相加
        long long RD_num = 0;
        for (int i = 0; i < M_L; i++) {
            long long a = 1;
            for (int j = i; j > 0; j--) {
                a *= N;
            }
            RD_num += (a * _M[i]);
        }

        // 相加
        D_num += RD_num;

        // 相加的数变回进制数，去判断回文及再次筛选
        M_L = 0;
        _M = toN(N, D_num, &M_L);
        
        /*判断是否是回文数*/
        // 得到对称长度
        int left_l;             // 对称左右长度
        if (M_L % 2 != 0) {    // 奇数进行加一操作
            left_l = M_L / 2 + 1;
        } else {                // 偶数不用
            left_l = M_L / 2;
        }

        // 开始判断
        int isFind = 1;
        for (int i = 0; i < left_l; i++) {
            if (_M[i] != _M[M_L - i - 1]) {
                isFind = 0;
                break;
            }
        }
        if (isFind) {
            break;
        } else if (STEP + 1 > 30) isMoreThirty = 1;
    }

    if (isMoreThirty) printf("Impossible!");
    else printf("STEP=%d", STEP);
    return 0;
}