[NOIP 1999 普及组] 回文数

知识点

高精度、进制运算、回文判断

解题思路

用低位在前的数位数组保存M。先检查是否回文，若是则0步；否则把当前数组与逆序数组逐位相加，在N进制下进位。每次相加后检查回文，最多进行30次，仍失败则输出Impossible!。

正确性说明

数位加法逐位保留余数、将商进到下一位，等价于当前数与其逆序数的准确N进制之和。步骤完全按题意执行，且在每次相加之前从0步起检查，首次回文对应最少步数；检查完第30步仍未成功即按规定无解。

易错点

进制可能16，A到F是数位；原数可能超过机器整数；30步包含第30步；真题输出为STEP=次数或Impossible!，不同于旧教材只输出次数。

复杂度

设L为迭代中的最大位数，时间O(30L)，空间O(L)，L最多比初始增加30。

参考代码（GNU C++17）

#include<bits/stdc++.h>
using namespace std;
int main(){ios::sync_with_stdio(false);cin.tie(nullptr);int b;string s;cin>>b>>s;vector<int>a;for(int i=(int)s.size()-1;i>=0;i--)a.push_back(isdigit(s[i])?s[i]-'0':s[i]-'A'+10);for(int step=0;step<=30;step++){bool pal=true;for(int i=0;i<(int)a.size();i++)if(a[i]!=a[a.size()-1-i])pal=false;if(pal){cout<<"STEP="<<step<<'\n';return 0;}if(step==30)break;vector<int>c;int carry=0;for(int i=0;i<(int)a.size();i++){int x=a[i]+a[a.size()-1-i]+carry;c.push_back(x%b);carry=x/b;}if(carry)c.push_back(carry);a.swap(c);}cout<<"Impossible!\n";}