A1 高精度加法 • EH's Blog

题目情境#

题目链接：https://www.luogu.com.cn/problem/P1601 ↗

题目描述：

高精度加法，相当于 a+b problem，不用考虑负数。

输入格式：

分两行输入。 $a,b\le 10^{500}$ 。

输出格式：

输出只有一行，代表 $a+b$ 的值。

输入输出样例：

输入 #1

1
1

plaintext

输出 #1

plaintext

输入 #2

1001
9099

plaintext

输出 #2

plaintext

算法解析#

高精度计算实际上用数组存储和模拟运算。

高精度加法的步骤：

高精度数字利用字符串读入；
把字符串翻转存入两个整型数组 A,B；
从低位到高位，累加，进位，存余；
把数组 C 从高位到低位依次输出。

时间复杂度O(n)

Python代码实现#


a = int(input())
b = int(input())
print(a + b)

python

C++代码实现#

#include <iostream>
using namespace std;

const int N=505;
int a[N],b[N],c[N];
int la,lb,lc;

void add(int a[],int b[],int c[]){ //a+b=c
    for(int i=1; i<=lc; i++){
        c[i]+=a[i]+b[i]; //求和
        c[i+1]+=c[i]/10; //进位
        c[i]%=10;        //存余
    }
    if(c[lc+1]) lc++;  //最高位
}
int main(){
    string sa,sb; cin>>sa>>sb;
    la=sa.size(),lb=sb.size(),lc=max(la,lb);
    for(int i=1; i<=la; i++) a[i]=sa[la-i]-'0';
    for(int i=1; i<=lb; i++) b[i]=sb[lb-i]-'0';
    add(a,b,c);
    for(int i=lc; i; i--) printf("%d",c[i]);
    return 0;
}