当前位置：首页 > article >正文

洛谷 P1015：回文数 ← 高精度加法

article 2025/2/11 9:37:58

【题目来源】
https://www.luogu.com.cn/problem/P1015
https://www.acwing.com/problem/content/5511/

【题目描述】
若一个数（首位不为零）从左向右读与从右向左读都一样，我们就将其称之为回文数。
例如：给定一个十进制数 56，将 56 加 65（即把 56 从右向左读），得到 121 是一个回文数。
又如：对于十进制数 87：
STEP1：
87+78=165
STEP2：
165+561=726
STEP3：
726+627=1353
STEP4：
1353+3531=4884
在这里的一步是指进行了一次 N 进制的加法，上例最少用了 4 步得到回文数 4884。
写一个程序，给定一个 N（2≤N≤10 或 N=16）进制数 M（100 位之内），求最少经过几步可以得到回文数。如果在 30 步以内（包含 30 步）不可能得到回文数，则输出 Impossible!。

【输入格式】
两行，分别是 N，M。

【输出格式】
如果能在 30 步以内得到回文数，输出格式形如 STEP=ans，其中 ans 为最少得到回文数的步数。
否则输出 Impossible!。

【输入样例】
10
87

【输出样例】
STEP=4

【算法分析】
● 高精度加法：https://blog.csdn.net/hnjzsyjyj/article/details/144656955
因为给定的数可达 100 位，故需使用高精度算法。
高精度加法代码模板如下所示：

#include <bits/stdc++.h>
using namespace std;
 
string hiAdd(string a,string b) {
    string c;
    int t=0;
    int i=a.size()-1,j=b.size()-1;
    while(i>=0 || j>=0) {
        if(i>=0) t+=(a[i]-'0');
        if(j>=0) t+=(b[j]-'0');
        c+=(t%10+'0');
        t/=10;
        i--,j--;
    }
    if(t!=0) c+=(t+'0');
    reverse(c.begin(),c.end());
    return c;
}
 
int main() {
    string a,b;
    cin>>a>>b;
    cout<<hiAdd(a,b)<<endl;
 
    return 0;
}
 
/*
in:
11 99

out:
110
*/

● 前导 0：https://blog.csdn.net/hnjzsyjyj/article/details/143719009
%nd → 表示输出的整数宽度至少为 n 位，不足 n 位左填充空格。位数大于 n 则输出实际位数。
%0nd → 表示输出的整数宽度至少为 n 位，不足 n 位左填充 0。位数大于 n 则输出实际位数。

#include <bits/stdc++.h>
using namespace std;
 
int main() {
    int x=12;
    printf("%05d",x);
    printf("\n");
    printf("%5d",x);
 
    printf("\n\n");
 
    int y=123456789;
    printf("%05d",y);
    printf("\n");
    printf("%5d",y);
 
    return 0;
}
 
/*
00012
   12
123456789
123456789
*/

【100分代码：有考虑16进制】

#include <bits/stdc++.h>
using namespace std;

int n;
string m;

bool check(string x) {
    string s=x;
    reverse(s.begin(),s.end());
    return s==x;
}

string hiAdd(string a) {
    string b=a;
    reverse(b.begin(), b.end());

    int t=0,x,y;
    for(int i=a.size()-1; i>=0; i--) {
        if(a[i]>='A' && a[i]<='F') {
            x=a[i]-'A'+10;
        } else x=a[i]-'0';

        if(b[i]>='A' && b[i]<='F') {
            y=b[i]-'A'+10;
        } else y=b[i]-'0';

        x=x+y+t;
        if(x>=n) { //x>=n,not x>n
            t=1;
            x-=n;
        } else t=0;

        if(x>9) a[i]=x-10+'A';
        else a[i]=x+'0';
    }
    if(t==1) a="1"+a;
    return a;
}

int main() {
    cin>>n>>m;
    for(int i=0; i<=30; i++) {
        if(check(m)) {
            cout<<"STEP="<<i<<endl;
            return 0;
        } else m=hiAdd(m);
    }
    cout<<"Impossible!"<<endl;

    return 0;
}

/*
in:
16
AC27

out:
STEP=6
*/

【75分代码：未考虑16进制】
此代码对了 3 个样例，错了 1 个样例，得 75 分。原因在于没有考虑 16 进制的情况。
此 75 分代码胜在可以把之前所讲的高精度加法的模板代码略加改动后，直接套用，思路简单。

#include <bits/stdc++.h>
using namespace std;

bool check(string x) {
    string s=x;
    reverse(s.begin(),s.end());
    return s==x;
}

string hiAdd(int k,string x) {
    string a=x;
    reverse(x.begin(),x.end());
    string b=x;
    string c;
    int t=0;
    int i=a.size()-1,j=b.size()-1;
    while(i>=0 || j>=0) {
        if(i>=0) t+=(a[i]-'0');
        if(j>=0) t+=(b[j]-'0');
        c+=(t%k+'0');
        t/=k;
        i--,j--;
    }
    if(t!=0) c+=(t+'0');
    reverse(c.begin(),c.end());
    return c;
}

int main() {
    int n;
    string m;
    cin>>n>>m;
    for(int i=0; i<=30; i++) {
        if(check(m)) {
            cout<<"STEP="<<i<<endl;
            return 0;
        } else m=hiAdd(n,m);
    }
    cout<<"Impossible!"<<endl;

    return 0;
}

/*
in:
16
AC27

out:
STEP=6
*/

【参考文献】
https://blog.csdn.net/hnjzsyjyj/article/details/144656955
https://blog.csdn.net/hnjzsyjyj/article/details/145522672
https://blog.csdn.net/hnjzsyjyj/article/details/144703201
https://www.cnblogs.com/yuzec/p/14410677.html

查看全文

http://www.kler.cn/a/540478.html