huangze21 @ 2023-08-16 10:31:13
#include <iostream>
#include <string>
#include <sstream>
using namespace std;
template <typename T>
string to_string(T value) {
ostringstream os;
os << value;
return os.str();
}
bool isPalindrome(string num){//判断是不是回文
int left = 0,right=num.length()-1;
while(left<right){
if(num[left]!=num[right]){
return false;
}
left++;
right--;
}
return true;
}
string addReverse(int base,string num){//将给定的字符串与其反转字符串逐位相加
int n = num.length();
string reverseNum;
for(int i=n-1;i>=0;i++){
reverseNum+=num[i];//给定字符串反转后的字符串
}
int carry = 0;//存储进位
string sum;//存储逐位相加后的字符串
for(int i=0;i<n;i++){
int digitSum=num[i]-'0'+reverseNum[i]-'0'+carry;
sum+=to_string(digitSum%base);//逐位相加后对应的位
carry = digitSum/base;//逐位相加后对应的进位
}
if(carry>0){
sum+=to_string(carry);
}
return sum;
}
int numOfSteps(int base, string num){
int steps=0;
while(!isPalindrome(num) && steps<=30){
num=addReverse(base,num);
steps++;
}
return (steps<=30)?steps:-1;
}
int main(){
int base;
string num;
cin >> base >> num;
int steps=numOfSteps(base,num);
if(steps!=-1)
cout << "STEP=" << steps << endl;
else
cout << "Impossible!" << endl;
return 0;
}