A31033.回文数 详细题解

当你看到m的长度不超过100时，就知道又要用高精度了

总结题目所涉及到的知识点： 高精度 + 模拟

这道题需要考虑的一个主要的点：

n进制的高精度加法

需不需要把非十进制的数全都转成十进制呢？
答：完 全 不 需 要 ！！！

原因：题目只是让我们求每次计算最后的结果是不是回文数，没有说让我们判断最后结果的十进制是不是回文数，并且在所有操作中是完全不需要转进制的

既然不需要转进制，那n进制的加法有应当怎么计算呢？

也是挺简单的，既然十进制满十进一，那么n进制就是满n进一
那么在高精度加法中，我的操作是先把a[i] + b[i] = c[i]这个操作弄完，再去搞进位（你们也可以根据自己的代码去调整，毕竟每个人的习惯和风格都不同）

这是十进制的操作：

if(c[i] >= 10)
{
    c[i + 1] += c[i] / 10;
    c[i] %= 10;
}

那我们就把十换成n不就行了吗，换汤不换药嘛

if(c[i] >= n)
{
    c[i + 1] += c[i] / n;
    c[i] %= n;
}

把这个点解决了，剩下的就简单了

上代码！（代码还有详细注释）

#include <bits/stdc++.h>
using namespace std;
int n,m_len = 0;
string m;
int a[550] = {0},b[550] = {0},c[550] = {0};
int lena = 0, lenb = 0, lenc = 0;
//正片（高精度加法）
void f()
{
    lenc = 0;//要初始化呀！！！
    memset(c,0,sizeof(c));//不初始化的话数组里边就会有上一次计算的数在里面啦！！！
    int max_len = max(lena,lenb);
    for(int i = 1;i <= max_len;i++)
    {
        c[++lenc] = a[i] + b[i];
    }
//处理进位
    for(int i = 1;i <= lenc;i++)
    {
        if(c[i] >= n)
        {
            c[i + 1] += c[i] / n;
            c[i] %= n;
        }
    }
    if(c[lenc + 1])//如果最高位还有进位，就要增加一个位置（如果最高位还有进位，c[lenc + 1]这个位置是1）
    {
        lenc++;
    }
//把结果复制给a预备下一轮的计算
    lena = lenc;
    for(int i = 1;i <= lenc;i++)
    {
        a[i] = c[i];
    }
}
//判断是否是回文数
bool is_huiwen()
{
    for(int i = 1;i <= lena;i++)
    {
        if (a[i] != a[lena - i + 1]) //a[i] != a[lena - i + 1]这条你们可以自己推，比较简单我就不多论述
        {
            return false;
        }
    }
    return true;
}
//字符转整型，方便计算
int char_turn(char ch)
{
    if (ch >= '0' && ch <= '9')
    { 
        return ch - '0';
    } 
    else
    {
        return ch - 'A' + 10;
    }   
}
int main()
{
    scanf("%d",&n);
    cin>>m;//这里不能用int数组，因为还有n>10的进制，这些进制是要用字母表示的
    m_len = m.size();
    for(int i = 0;i < m_len;i++)
    {
        a[m_len - i] = char_turn(m[i]);
    }
    lena = m_len;
    for(int step = 1;step <= 30;step++)
    {
        lenb = lena;
        for(int i = 1;i <= lena;i++)
        {
            b[i] = a[lena - i + 1];
        }
        f();
        if(is_huiwen())
        {
            printf("STEP=%d",step);
            return 0;
        }
    }
    printf("Impossible!");
//如果次数是小于等于30的早就已经在上面return 0；了，直接输出就好了
    return 0;
}

提醒：不要复制！！！