题解 | #[NOIP1999]回文数#

#include <iostream>
#include <cmath>
#include <string>
using namespace std;

bool hw(string num){
    for(long long i=0;i<num.length();i++){
        if (num[i]!=num[num.length()-1-i])
        {
            return false;
        }
        
    }
    return true;
}

int changeMto10(string num,int num1){
    long long sum = 0;
    string a = "0123456789ABCDEFG";
    for(int i=0;i<num.length();i++){
        for(int j=0;j<a.length();j++){
            if(num[i]==a[j]){
                sum+= j * pow(num1,num.length()-1-i);
            }
        }
    }

    return sum;
}

string changetoN(int n, int num) {
    string result = "";
    string hexChars = "0123456789ABCDEF"; // 十六进制字符

    if (n == 0) {
        return "0";
    }

    while (n > 0) {
        int remainder = n % num;
        result = hexChars[remainder] + result;
        n /= num;
    }

    return result;
}

string backtobegin(string a){
    string b = a;
    for(int i=0;i<a.length();i++){
        b[i]=a[a.length()-1-i];
    }
    return b;
}

int main() {
    int ans=0;
    int N;
    string M;
    cin>>N>>M;
    //输入进制N，大于等于10时由A,B...表示，N1为N的数字表示，16为G
    
    if (N<2 || (N>10 && N!=16))
    {
        return 0;//确保2<=N<=10或N=16
    }else{
        if(N!=10){
        for(int i=0;i<1000;i++){
            string M1=backtobegin(M);
            long long sum=changeMto10(M,N)+changeMto10(M1,N);
            ans++;
            string strM = changetoN(sum,N);
            if (hw(strM))
            {
                break;
            }else{
                 M = strM;
            }
        }
        }else{
            for(int i=0;i<1000;i++){
            string M1=backtobegin(M);
            long long a = stoll(M)+stoll(M1);
            ans++;
             string strM =to_string(a);
             if (hw(strM))
            {
                break;
            }else{
                 M = strM;
            }
        }
        }
    }
    if(ans<=30){
        cout<<"STEP="<<ans;
    }else{
        cout<<"Impossible!";
    }
    
    
}