若一个数（首位不为零）从左向右读与从右向左读都一样，我们就将其称之为回文数。
STEP1：87+78 = 165 STEP2：165+561 = 726
STEP3：726+627 = 1353 STEP4：1353+3531 = 4884
在这里的一步是指进行了一次N进制的加法，上例最少用了4步得到回文数4884。
进制N>10时，使用大写'A'字母表示10，'B'表示11,...,'E'表示15
两行，分别为N,M
STEP=ans
9 87
STEP=6
#include <stdio.h>
#include <string.h>
#define MAX_DIGITS 100
// 将字符转换为对应的数值
int char_to_int(char c) {
//0~9
if (c >= '0' && c <= '9'){
return c - '0';
}
//10~16
else
return c - 'A' + 10;
}
// 将数值转换为对应的字符
char int_to_char(int n) {
if (n < 10) {
return n + '0';
}
//n > 10, 10 == 'A'.....
else
return n - 10 + 'A';
}
// 反转字符串
void reverse_string(char *str) {
int len = strlen(str);
for (int i = 0; i < len / 2; i++) {
char temp = str[i];
str[i] = str[len - 1 - i];
str[len - 1 - i] = temp;
}
}
// 检查是否为回文
int is_palindrome(char *str) {
int len = strlen(str);
for (int i = 0; i < len / 2; i++) {
if (str[i] != str[len - 1 - i]){
return 0;
}
}
return 1;
}
// 在指定进制下将两个数相加
void add_numbers(char *num1, char *num2, char *result, int base) {
//carry存储进位
int carry = 0;
int i = strlen(num1) - 1;
int j = strlen(num2) - 1;
int k = 0;
while (i >= 0 || j >= 0 || carry) {
int sum = carry;
if (i >= 0) sum += char_to_int(num1[i--]);
if (j >= 0) sum += char_to_int(num2[j--]);
result[k++] = int_to_char(sum % base); //当前位的数字
carry = sum / base; //需要进位的值
}
result[k] = '\0';
reverse_string(result);
}
// 主要逻辑函数
int find_palindrome_steps(char *num, int base) {
char reversed[MAX_DIGITS];
char sum[MAX_DIGITS];
for (int step = 1; step <= 30; step++) {
//将数字拷贝
strcpy(reversed, num);
//进行反转
reverse_string(reversed);
//指定进制下相加
add_numbers(num, reversed, sum, base);
if (is_palindrome(sum)) {
return step;
}
strcpy(num, sum);
}
return -1; // Impossible in 30 steps
}
int main() {
int base;
char num[MAX_DIGITS];
scanf("%d", &base);
scanf("%s", num);
int steps = find_palindrome_steps(num, base);
if (steps == -1) {
printf("Impossible!\n");
} else {
printf("STEP=%d\n", steps);
}
return 0;
} 
#include <stdbool.h>
#include <stdio.h>
long sum_decimal(char *p, long length, long radix);
long to_radixOfN(char *p, long sum, long radix);
_Bool isPalindrome(char *p, long length);
//有一个用例是10进制89，需要24步，如果用int很快就不够，会高位截断，结果不对，所以用long;
int main() {
char arr[101] = {0}, temp;
long radix, steps = 0, index = 0, sum = 0, new_index = 0;
scanf("%ld", &radix);
getchar();
while((temp = getchar()) != '\n'){
arr[index++] = temp;
}
while(steps <= 30){
sum = sum_decimal(arr, index, radix);
steps++;
new_index = to_radixOfN(arr, sum, radix);
if(isPalindrome(arr, new_index)){
printf("STEP=%ld\n", steps);
break;
}
index = new_index;
}
if(steps > 30){
printf("Impossible!");
}
return 0;
}
long sum_decimal(char *p, long length, long radix){
long result = 0, multi = 1;
for(long i = 0; i < length; i++){
if(p[i] >= '0' && p[i] <= '9'){
result += multi * (p[i] - '0');
} else {
result += multi * (p[i] - 55);
}
multi *= radix;
}
multi = 1;
for(long i = length - 1; i >= 0; i--){
if(p[i] >= '0' && p[i] <= '9'){
result += multi * (p[i] - '0');
} else {
result += multi * (p[i] - 55);
}
multi *= radix;
}
return result;
}
long to_radixOfN(char *p, long sum, long radix){
long length = 0;
while(sum){
if(sum % radix >= 10){
p[length++] = sum % radix + 55;
} else {
p[length++] = sum % radix + '0';
}
sum /= radix;
}
return length;
}
_Bool isPalindrome(char *p, long length){
long left = 0, right = length - 1;
while(left < right){
if(p[left] == p[right]){
left++, right--;
} else {
return false;
}
}
return true;
} 
#include <stdio.h>
int pld(char M[], int* l) {//判断回文数
int left = 0;
int right = *l;
for (; left < right; left++, right--) {
if (M[left] != M[right])
return 1;
}
return 0;
}
void add(char M[], int* l, int n) {//对数字进行处理（反序相加，1-16进制皆可）
int i = 0;
int j = *l;
int sum = 0;
char M1[100];
for (i = 0; i <= *l; i++, j--)//创建新数组保存反序后的数
M1[i] = M[j];
for (i = 0; i <= *l; i++) {//处理十进制以上的数
if (M[i] > 57)
M[i] -= 7;
if (M1[i] > 57)
M1[i] -= 7;
}
for (i = 0; i <= *l; i++) {
sum = M[i] + M1[i] - 96;
M[i] = (sum % n + 48);//两个数相加取模n进制
if (i == *l) {//判断如果两个数的首尾相加有进位，l就加一（l记录这个数有几位数）
if ((sum / n) != 0) {
M[i + 1] = (sum / n + 48);
(*l)++;
}
break;
}
M[i + 1] = (sum / n + 48) + M[i + 1] - 48;//两个数相加的进位加到前一位去（没有进位就是加0）
}
for (i = 0; i <= *l; i++) {//处理十进制以上的数
if (M[i] > 57)
M[i] += 7;
}
}
int main() {
int n = 0;
int l = 0;
int step = 0;
char M[100];
scanf("%d", &n);
getchar();
int i = 0;
do {
M[i] = getchar();//将数字读入数组里
i++;
} while (M[i - 1] != '\n');
i -= 2;
l = i;//l是记录这个数有几位数
int left = 0;
int right = l;
do {//将数组里数字反序（这里是方便后面进位才反序的，实际的反序相加处理在后面的函数里）
int tmp = 0;
tmp = M[left];
M[left] = M[right];
M[right] = tmp;
} while (left++ < right--);
while (pld(M, &l)) {//如果不是回文数就继续反序相加处理
add(M, &l, n);
step++;
if (step > 30)//处理步数大于30就跳出循环
break;
}
if (step <= 30)
printf("STEP=%d", step);
else
printf("Impossible!");
return 0;
} 
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
typedef unsigned long long ull;
// 逆序，只能10进制数
ull reverse(ull n) {
ull sum = 0;
while (n != 0) {
sum = sum * 10 + n % 10;
n /= 10;
}
return sum;
}
// 逆序，只能16进制数
ull reverse_16(ull n) {
int i, len = 0;
ull m = n;
char tmp;
while (m != 0) {
len++;
m = m / 10;
}
char* str = (char*)calloc(len + 1, sizeof(char));
sprintf(str, "%llX", n);
len = 0;
while (str[len] != '\0')
len++;
// printf("逆序前：%s\n",str);
for (i = 0; i < len / 2; i++) {
// printf("*(str+i)=%c *(str+(len-i))=%c\n",*(str+i),*(str+(len-1-i)));
tmp = *(str + i);
*(str + i) = *(str + (len - 1 - i));
*(str + (len - 1 - i)) = tmp;
}
// printf("逆序后：%s\n",str);
sscanf(str, "%llX", &m);
// printf("m=%llu\n", m);
free(str);
return m;
}
// 2<=n<=10 进制转10进制,
ull n2ten(ull a, int n) {
ull y = 0, i = 1;
while (a != 0) {
y = y + (a % 10) * i;
a /= 10;
i = i * n;
}
return y;
}
// 10进制数转为n进制 2<=n<=10
ull ten2n(ull a, int n) {
ull sum = 0;
int str[100] = {0};
int count = 0, i = 0;
do {
str[count] = a % n;
a /= n;
count++;
} while (a != 0);
for (i = count - 1; i >= 0; i--)
sum = sum * 10 + str[i];
return sum;
}
// 判断是否是回文数，只能是10进制数，1，是；0，不是
int isPalindrome(ull n) {
int i, len = 0;
ull m = n;
while (m != 0) {
len++;
m = m / 10;
}
char* str = (char*)calloc(len + 1, sizeof(char));
sprintf(str, "%llu", n);
for (i = 0; i < len / 2; i++) {
// printf("*(str+i)=%c *(str+(len-i))=%c\n",*(str+i),*(str+(len-1-i)));
if (*(str + i) != *(str + (len - 1 - i))) {
free(str);
return 0;
}
}
free(str);
return 1;
}
// 判断是否是回文数，只能是16进制数，1，是；0，不是
int isPalindrome_16(ull n) {
int i, len = 0;
ull m = n;
while (m != 0) {
len++;
m = m / 10;
}
char* str = (char*)calloc(len + 1, sizeof(char));
sprintf(str, "%llX", n);
//printf("len=%d %s\n", len,str);
len = 0;
while (str[len] != '\0')
len++;
//printf("len=%d %s\n", len,str);
for (i = 0; i < len / 2; i++) {
//printf("*(str+i)=%c *(str+(len-i))=%c\n", *(str + i), *(str + (len - 1 - i)));
if (*(str + i) != *(str + (len - 1 - i))) {
free(str);
return 0;
}
}
free(str);
return 1;
}
int main() {
ull a, ac;
int b;
ull tmp;
int i = 0;
scanf("%d", &b);
if (b == 16) {
scanf("%llX", &a);
} else if (b >= 2 && b <= 10) {
scanf("%llu", &a);
}
ac = a;
if (b == 16) {
while (1) {
i++;
tmp = ac + reverse_16(ac);
//printf("10:%lld %d:%llX\n", tmp, b, tmp);
if (isPalindrome_16(tmp)) {
printf("STEP=%d\n", i);
return 0;
}
if (i > 30) {
printf("Impossible!");
return 0;
}
ac = tmp;
}
} else {
while (1) {
i++;
tmp = n2ten(ac, b) + n2ten(reverse(ac), b);
//printf("10:%lld %d:%lld\n", tmp, b, ten2n(tmp, b));
if (isPalindrome(ten2n(tmp, b))) {
printf("STEP=%d\n", i);
return 0;
}
if (i > 30) {
printf("Impossible!");
return 0;
}
ac = ten2n(tmp, b);
}
}
return 0;
}
#include<stdio.h>
#include<stdbool.h>
#include<math.h>
#include<string.h>
char c[100] = {0};
bool IsPalindrome(char* p, int len)
{
int left = 0;
int right = len - 1;
while ((left) < (right))
{
if (p[left++] != p[right--])
return false;
}
return true;
}
int getInt(char n)//将'0'-'9'转换为0-9；'a'-'z'转换成10-35
{
if (n >= '0' && n <= '9')
return n - '0';
else
{
return n - 'A' + 10;
}
}
char getChar(int n)//将0-9转换为'0'-'9';a-z转换成’a'-‘z'
{
if (n >= 0 && n <= 9)
return n + '0';
else
return n - 10 + 'A';
}
void Add(char* a,int N,int len)
{
int sum1 = 0;
int sum2 = 0;
int tail = 0;
int begin = 0;
int end = len - 1;
int i = 0;
while (end >= 0)
{
sum1 = getInt(a[begin]);
sum2 = getInt(a[end]);
c[i] = getChar((sum1+sum2+tail)%N);
tail = (sum1 + sum2 + tail) / N;
end--;
begin++;
i++;
}
while (tail > 0)
{
c[i] = getChar(tail % N);
tail /= N;
i++;
}
}
int main()
{
char a[100] = {0};
int N = 0;
scanf("%d", &N);
getchar();
scanf("%s", a);
int len = strlen(a);
if (IsPalindrome(a, len))
{ printf("STEP=%d\n",1);
return 1;
}
int count = 0;
while (!IsPalindrome(a,len))
{
Add(a,N,len);
strcpy(a,c);
len = strlen(c);
count++;
if (count >= 31)
{
printf("Impossible!\n");
return 0;
}
}
printf("STEP=%d\n",count);
return 0;
} 
#include<stdio.h>
void transform(char ch1[100],int ch_1[100],int i)
{
for (int j = 0; j <= i; j++)
{
switch (ch1[j])
{
case 'A':
ch_1[j] = 10;
break;
case 'B':
ch_1[j] = 11;
break;
case 'C':
ch_1[j] = 12;
break;
case 'D':
ch_1[j] = 13;
break;
case 'E':
ch_1[j] = 14;
break;
case 'F':
ch_1[j] = 15;
break;
default:
ch_1[j] = ch1[j] - '0';
break;
}
}
}
int Add(char ch1[100], char ch2[100],char sum[100],int i,int n)
{
//对数组进行变换，由char型变为int型
int ch_1[100] = { 0 };
int ch_2[100] = { 0 };
transform(ch1, ch_1, i);
transform(ch2, ch_2, i);
int j = 0;
while (i>=0)
{
int tmp = ch_1[j] + ch_2[j];
if (tmp < n&&n>10)
{
switch (tmp)
{
case 10:
sum[j] = 'A';
break;
case 11:
sum[j] = 'B';
break;
case 12:
sum[j] = 'C';
break;
case 13:
sum[j] = 'D';
break;
case 14:
sum[j] = 'E';
break;
case 15:
sum[j] = 'F';
break;
default:
sum[j] = tmp + '0';
break;
}
}
else if (tmp<n&&n<=10)
{
sum[j] = tmp + '0';
}
else if (tmp >= n && n > 10)
{
ch_1[j + 1] += 1;
switch (tmp%n)
{
case 10:
sum[j] = 'A';
break;
case 11:
sum[j] = 'B';
break;
case 12:
sum[j] = 'C';
break;
case 13:
sum[j] = 'D';
break;
case 14:
sum[j] = 'E';
break;
case 15:
sum[j] = 'F';
break;
default:
sum[j] = tmp%n + '0';
break;
}
}
else if (tmp >= n && n <= 10)
{
ch_1[j + 1] += 1;
sum[j] = tmp % n+'0';
}
i--;
j++;
}
if (ch_1[j] > 0)
sum[j] = ch_1[j] + '0';
else
j = j - 1;
//再颠倒
int left = 0;
int right = j;
while (left <= right)
{
char ret = sum[left];
sum[left] = sum[right];
sum[right] = ret;
left++;
right--;
}
return j;
}
int is_pan(char sum[100],int j)
{
int left = 0;
int right = j;
while (left <= right)
{
if (sum[left] != sum[right])
return 0;
left++;
right--;
}
return 1;
}
int main()
{
//搞明白自己的错误点，逆序和进制没有关系，不能把所有的数转化为10进制再运算。
//由于有16等进制的存在，所以要获取字符，而不是数字
int n;
char ch1[100] = { 0 };
char ch2[100] = { 0 };
int i = 0;
int count = 1;
scanf("%d", &n);
getchar();
while (scanf("%c", &ch1[i])!=EOF)
{
if (ch1[i] == '\n')
break;
i++;
}
i = i - 1;
//逆序，逆序之后再做进制运算
//用一个新数组存
while (1)
{
char sum[100] = { 0 };
int j = 0;
int tmp = i;
for (j = 0; j <= i; j++)
{
ch2[j] = ch1[tmp];
tmp--;
}
int ret = Add(ch1, ch2, sum, i, n);
//已经得到sum[];
int out = is_pan(sum, ret);
if (out == 1)
{
printf("STEP=%d\n", count);
break;
}
else
{
i = ret;
for (j = 0; j <= ret; j++)
{
ch1[j] = sum[j];
}
count++;
if (count > 30)
{
printf("Impossible!\n");
break;
}
continue;
}
}
return 0;
} 
#include<stdio.h>
#include<stdbool.h>
#include<string.h>
bool judge(char*p,int n)//判断回文数
{
for(int i=0;i<n/2;i++)
{
if(p[i]!=p[n-1-i])
return false;
}
return true;
}
void STEP(char*M1,int len,int N)
{
int m=0,n=0;
char M2[100];
char* p=M2;
for(int i=0;i<len;i++)
{
int n1,n2;
if(M1[i]>='0'&&M1[i]<='9')
n1=M1[i]-48;
else
n1=M1[i]-'A'+10;
if(M1[len-i-1]>='0'&&M1[len-i-1]<='9')
n2=M1[len-i-1]-48;
else
n2=M1[len-i-1]-'A'+10;
n=n1+n2;
if(m!=0)
n++;
m=n/N;
n=n%N;
if(n<10)
*p=(char)(n+48);
else
*p='A'+n-10;
p++;
}
if(m==1)
*p=(char)(m+48),p++;
*p='\0';
int len2=strlen(M2);
for(int i=0;i<len2;i++)
{
M1[i]=M2[len2-1-i];
}
M1[len2]='\0';
}
int main()
{
int N,i;
char M1[100];
scanf("%d%s",&N,M1);
int len=strlen(M1);
for( i=0;i<31;i++)
{
STEP(M1,strlen(M1),N);
if(judge(M1,strlen(M1)))
break;
}
if(i<31)
printf("STEP=%d",i+1);
else
printf("Impossible!");
return 0;
}
一个地方的范围写错了，横看左看感觉都是对的，调试一个多小时糟心啊(lll￢ω￢)
扫描二维码，关注牛客网
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
京公网安备
11010502036488号
