回文数

回文数

题目描述

若一个数（首位不为零）从左向右读与从右向左读都一样，我们就将其称之为回文数。

例如：给定一个十进制数 565656 ，将 565656 加 656565 （即把 565656 从右向左读），得到 121121121 是一个回文数。

又如：对于十进制数 878787 ：

step1： 878787 + 787878 = 165165165

STEP2： 165165165 + 561561561 = 726726726

STEP3： 726726726 + 627627627 = 135313531353

STEP4： 135313531353 + 353135313531 = 488448844884

在这里的一步是指进行了一次 NNN 进制的加法，上例最少用了 444 步得到回文数 488448844884 。

写一个程序，给定一个 NNN ( 2≤N≤10,N=162 \le N \le 10,N=162≤N≤10,N=16 )进制数 MMM ( 100100100 位之内)，求最少经过几步可以得到回文数。如果在 303030 步以内（包含 303030 步）不可能得到回文数，则输出Impossible!

输入输出格式

两行，分别是 N ， M 。

输出格式：

STEP=ans

输入输出样例

输入样例#1：复制

10
87

输出样例#1：复制

STEP=4

标程：

#include <iOStream>
#include <cstdio>
#include <string>
using namespace std;
unsigned long long n=0,k,len,nex;
string nn;
bool wow(unsigned long long a)//把数倒过来，再相加
{
    unsigned long long s=0;
    for (unsigned long long i=a;i;i/=k)
        s=s*k+i%k;//值得学习
    nex=s+a;
    return s==a;
}//如果s==a返回真，否则为假。新用法
unsigned long long ch(char a)
{
    if (a>='0' && a<='9') return a-'0';
    return a-'A'+10;
}
int main()
{
    cin>>k>>nn;len=nn.size();
    for (int i=0;i<len;i++)
        n=n*k+ch(nn[i]);//转成数字
    unsigned long long step;
    for (step=0;!wow(n) && step<=30;step++)//！wow（）就是s！=a;
        n=nex;
    if (step<=30) cout<<"STEP="<<step<<endl;
    else cout<<"Impossible!";
    return 0;
}

相关阅读