高精度加法

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

输入格式

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

输出格式

共一行，包含所求的和。

数据范围

$1\le \mathrm{整}\mathrm{数}\mathrm{长}\mathrm{度}\le 100000$

输入样例

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 == 1) C.push_back(t);

    return C;
}

int main() {
    string a, b;
    cin >> a >> b;

    vector<int> A, B;
    for(int i = a.size() - 1; i >= 0; i--) A.push_back(a[i] - '0');
    for(int i = b.size() - 1; i >= 0; i--) B.push_back(b[i] - '0');

    auto C = add(A, B);

    for(int i = C.size() - 1; i >= 0; i--) cout << C[i];

    return 0;
}

高精度减法

给定两个正整数（不含前导 $0$），计算它们的差，计算结果可能为负数。

输入格式

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

输出格式

共一行，包含所求的差。

数据范围

$1\le \mathrm{整}\mathrm{数}\mathrm{长}\mathrm{度}\le {10}^6$

输入样例

32
11

输出样例

21

#include <iostream>
#include <vector>
using namespace std;

// a >= b
bool cmp(string &a, string &b) {
    if(a.size() != b.size()) return a.size() > b.size();
    for(int i = 0; i < a.size(); i++)
        if(a[i] != b[i])
            return a[i] > b[i];
    return true;
}

// C = A - B
vector<int> sub(vector<int>& A, vector<int>& B) {
    vector<int> C;

    int t = 0;
    for(int i = 0; i < A.size(); i++) {
        t = A[i] - t;
        if(i < B.size()) t -= B[i];
        C.push_back((t + 10) % 10);
        if(t < 0) t = 1;
        else t = 0;
    }

    // 去除前导0
    while(C.size() > 1 && C.back() == 0) C.pop_back();

    return C;
}

int main() {
    string a, b;
    cin >> a >> b;

    vector<int> A, B;
    for(int i = a.size() - 1; i >= 0; i--) A.push_back(a[i] - '0');
    for(int i = b.size() - 1; i >= 0; i--) B.push_back(b[i] - '0');

    vector<int> C;
    if(cmp(a, b)) {
        C = sub(A, B);
    } else {
        C = sub(B, A);
        cout << "-";
    }

    for(int i = C.size() - 1; i >= 0; i --) cout << C[i];

    return 0;
}

高精度乘法

高精度乘低精度

给定两个非负整数（不含前导 $0$） $A$ 和 $B$，请你计算 $A\times B$ 的值。

输入格式

共两行，第一行包含整数 $A$，第二行包含整数 $B$。

输出格式

共一行，包含 $A\times B$ 的值。

数据范围

$1\le A\mathrm{的}\mathrm{长}\mathrm{度}\le 100000,0\le B\le 100000$

输入样例

2
3

输出样例

6

#include <iostream>
#include <vector>
using namespace std;

vector<int> mul(vector<int> &A, int b) {
    vector<int> C;

    int t = 0;
    for(int i = 0; i < A.size(); i++) {
        t += A[i] * b;
        C.push_back(t % 10);
        t /= 10;
    }

    while(t) {
        C.push_back(t % 10);
        t /= 10;
    }

    // 去除前导零
    while(C.size() > 1 && C.back() == 0) C.pop_back();

    return C;
}


int main() {
    string a;
    int b;
    cin >> a >> b;

    vector<int> A;
    for(int i = a.size() - 1; i >= 0; i--) A.push_back(a[i] - '0');

    auto C = mul(A, b);

    for(int i = C.size() - 1; i >= 0; i--) cout << C[i];

    return 0;
}

高精度乘高精度

给定两个非负整数（不含前导 $0$） $A$ 和 $B$，请你计算 $A\times B$ 的值。

输入格式

共两行，第一行包含整数 $A$，第二行包含整数 $B$。

输出格式

共一行，包含 $A\times B$ 的值。

数据范围

$1\le A\mathrm{的}\mathrm{长}\mathrm{度}\le 100000,1\le B\mathrm{的}\mathrm{长}\mathrm{度}\le 100000$

输入样例

36
3

输出样例

108

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

vector<int> mul(vector<int>& A, vector<int>& B) {
	vector<int> C(200000); // 最多 |A| + |B| 位

    for (int i = 0; i < A.size(); i++) { // 乘数
		for (int j = 0; j < B.size(); j++) { // 被乘数
			C[i + j] += A[i] * B[j];
			C[i + j + 1] += C[i + j] / 10;
			C[i + j] %= 10;
		}
	}

    // 去除前导0
    while (C.size() > 1 && C.back() == 0) C.pop_back();

	return C;
}

int main(){
	string a, b;
	cin >> a >> b;

	vector<int> A, B;
	for (int i = a.size() - 1; i >= 0; i--) A.push_back(a[i] - '0');
	for (int i = b.size() - 1; i >= 0; i--) B.push_back(b[i] - '0');

	vector<int> C = mul(A, B);

	for (int i = C.size() - 1; i >= 0; i--) cout << C[i];
	cout << endl;

	return 0;
}

高精度除法

高精度除低精度

给定两个非负整数（不含前导 $0$） $A$，$B$，请你计算 $A/B$ 的商和余数。

输入格式

共两行，第一行包含整数 $A$ ，第二行包含整数 $B$。

输出格式

共两行，第一行输出所求的商，第二行输出所求余数。

数据范围

$1\le A\mathrm{的}\mathrm{长}\mathrm{度}\le 100000,1\le B\le 100000,B\mathrm{一}\mathrm{定}\mathrm{不}\mathrm{为}0$

输入样例

``

7
2

输出样例

3
1

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

vector<int> div(vector<int>& A, int b, long long& r) {
    vector<int> C;

    r = 0;
    for(int i = A.size() - 1; i >= 0; i--) {
        r = r * 10 + A[i];
        C.push_back(r / b);
        r %= b;
    }
    reverse(C.begin(), C.end());
    for(int i = C.size(); i > 1 && C.back() == 0; i--) C.pop_back();

    return C;
}

int main() {
    string a;
    int b;
    cin >> a >> b;

    vector<int> A;
    for(int i = a.size() - 1; i >= 0; i--) A.push_back(a[i] - '0');

    long long r;
    vector<int> C = div(A, b, r);

    for(int i = C.size() - 1; i >= 0; i--) cout << C[i];
    cout << endl << r << endl;

    return 0;
}

高精度除高精度

给定两个非负整数（不含前导 $0$） $A$，$B$，请你计算 $A/B$ 的商和余数。

输入格式

共两行，第一行包含整数 $A$ ，第二行包含整数 $B$。

输出格式

共两行，第一行输出所求的商，第二行输出所求余数。

数据范围

$1\le A\mathrm{的}\mathrm{长}\mathrm{度}\le 100000,1\le B\mathrm{的}\mathrm{长}\mathrm{度}\le 100000,B\mathrm{一}\mathrm{定}\mathrm{不}\mathrm{为}0$

输入样例

1231312318457577687897987642324567864324567876543245671425346756786867867867
1231312318767141738178325678412414124141425346756786867867867

输出样例

999999999748590
179780909068307566598992807564736854549985603543237528310337

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

const int N = 1e6 + 10;

void copy(int x[], int y[], int offset) {
    for (int i = 1; i <= x[0]; i++) {
        y[i + offset] = x[i];
    }

    y[0] = x[0] + offset;
}

bool cmp(int x[], int y[]) {
    if (x[0] != y[0]) return x[0] > y[0];
    for (int i = 1; i <= x[0]; i++) {
        if (x[i] != y[i]) return x[i] > y[i];
    }

    return true;
}

void sub(int x[], int y[]) {
    for (int i = x[0]; i >= 1; i--) {
        if (x[i] < y[i]) {
            x[i] += 10;
            x[i - 1]--;
        }
        x[i] -= y[i];
    }
}

int main() {
    string a, b;
    cin >> a >> b;

    int A[N] = {0}, B[N] = {0}, C[N] = {0};
    A[0] = a.size(); // A[0] 存储被除数的位数
    B[0] = b.size(); // B[0] 存储除数的位数
    C[0] = A[0] - B[0] + 1; // C[0] 存储商的位数

    // 正序存储
    for (int i = 1; i <= A[0]; i++) A[i] = a[i - 1] - '0';
    for (int i = 1; i <= B[0]; i++) B[i] = b[i - 1] - '0';

    if (!cmp(A, B)) {
        cout << 0 << endl << a << endl;
        return 0;
    }

    int T[2 * N] = {0};
    for (int i = 1; i <= C[0]; i++) {
        memset(T, 0, sizeof T);
        copy(B, T, i - 1);

        A[0] = T[0];
        while (cmp(A, T)) {
            sub(A, T);
            C[i]++;
        }
    }

    int i = 1;
    while (i < C[0] && C[i] == 0) i++;
    for (; i <= C[0]; i++) cout << C[i];
    cout << endl;

    i = 1;
    while (i < A[0] && A[i] == 0) i++;
    for (; i <= A[0]; i++) cout << A[i];

    return 0;
}