高精度加法

一、算法思想

使用数组来存储大整数，为了方便处理进位，可以按照由低位到高位的顺序存储。

二、算法模板

C++

// C = A + B, A >= 0, B >= 0
vector<int> add(vector<int> &A, vector<int> &B)
{
    vector<int> C;
    
    int t = 0;
    for (int i = 0; i < A.size() || i < B.size(); i++) {
        if (i < A.size()) t += A[i];
        if (i < B.size()) t += B[i];
        C.push_back(t % 10);
        t /= 10;
    }
    if (t) C.push_back(1);
    
    return C;
}

Go

func add(A, B []int) (C []int) {
    t := 0
    for i := 0; i < len(A) || i < len(B); i++ {
        if i < len(A) {
            t += A[i]
        }
        if i < len(B) {
            t += B[i]
        }
        C = append(C, t%10)
        t /= 10
    }
    if t > 0 {
        C = append(C, t)
    }
    return
}

三、代码实战

AcWing 0791

---

题目：高精度加法

给定两个正整数（不含前导 $0$），计算它们的和。

输入格式

共两行，每行包含一个整数。

输出格式

共一行，包含所求的和。

数据范围

$1\le \text{整数长度} \le 10^5$

输入样例：

12

23

输出样例：

35

解答代码：

#include <iostream>
#include <vector>

using namespace std;

vector<int> add(vector<int> &A, vector<int> &B)
{
    vector<int> C;
    
    int t = 0;
    for (int i = 0; i < A.size() || i < B.size(); i++) {
        if (i < A.size()) t += A[i];
        if (i < B.size()) t += B[i];
        C.push_back(t % 10);
        t /= 10;
    }
    if (t) C.push_back(1);
    
    return C;
}

int main()
{
    string a, b;
    vector<int> A, B;
    
    cin >> a >> b;
    for (int i = a.length() - 1; i >= 0; i--) A.push_back(a[i] - '0');
    for (int i = b.length() - 1; i >= 0; i--) B.push_back(b[i] - '0');
    
    vector<int> C = add(A, B);
    for (int i = C.size() - 1; i >= 0; i--) printf("%d", C[i]);
    
    return 0;
}

package main

import (
    "bufio"
    . "fmt"
    "io"
    "os"
)

func add(A, B []int) (C []int) {
    t := 0
    for i := 0; i < len(A) || i < len(B); i++ {
        if i < len(A) {
            t += A[i]
        }
        if i < len(B) {
            t += B[i]
        }
        C = append(C, t%10)
        t /= 10
    }
    if t > 0 {
        C = append(C, t)
    }
    return
}

func run(_r io.Reader, out io.Writer) {
    in := bufio.NewReader(_r)

    var a, b string
    Fscan(in, &a, &b)

    var A, B []int
    for i := len(a) - 1; i >= 0; i-- {
        A = append(A, int(a[i]-'0'))
    }
    for i := len(b) - 1; i >= 0; i-- {
        B = append(B, int(b[i]-'0'))
    }

    C := add(A, B)
    for i := len(C) - 1; i >= 0; i-- {
        Fprintf(out, "%d", C[i])
    }
}

func main() {
    run(os.Stdin, os.Stdout)
}