高精度加法¶

两个大整数加法
包含小数的加法

既可以用链表来计算，也可以用数组来计算，具体见SJTU 1202 bigInt的解析

//洛谷P1601 A+B Problem
#include <iostream>
#include <iomanip>
#include <vector>
#include <string>
#include <queue>
#include <set>
#include <map>
#include <algorithm>
#include <cmath>
#include <climits>
#include <cstdio>

using namespace std;

int n = 205;
vector<int> num1(n), num2(n);
vector<int> res(n);

void init(vector<int> & v, string s)
{
    int len = s.size();
    v[0] = len;
    for (int i = 1; i <= len; ++i)
        v[i] = s[len - i] - '0';
}

void bigNumPlus(string & s1, string & s2)
{
    init(num1, s1);
    init(num2, s2);

    int pos = 1;
    int extra = 0;
    while (pos <= num1[0] || pos <= num2[0]) {
        res[pos] = num1[pos] + num2[pos] + extra;
        extra = res[pos] / 10;
        res[pos] %= 10;
        ++pos;
    }
    res[pos] = extra;
    //去除前导0
    while (res[pos] == 0 && pos > 1) --pos;

    for (int i = pos; i >= 1; --i)
        cout << res[i];
    cout << endl;
}

int main()
{
    std::ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    string s1, s2;
    cin >> s1 >> s2;
    bigNumPlus(s1, s2);

    return 0;
}

高精度减法¶

//洛谷P2142 高精度减法
#include <iostream>
#include <iomanip>
#include <vector>
#include <string>
#include <queue>
#include <set>
#include <map>
#include <algorithm>
#include <cmath>
#include <climits>
#include <cstdio>

using namespace std;

int n = 10100;
vector<int> num1(n), num2(n);
vector<int> res(n);

void init(vector<int> & v, string & s)
{
    int len = s.size();
    v[0] = len;
    for (int i = 1; i <= len; ++i)
        v[i] = s[len - i] - '0'; //倒序存储
}

void bigNumMinus(string & s1, string & s2)
{
    init(num1, s1);
    init(num2, s2);

    int pos = 1;
    while (pos <= num1[0] || pos <= num2[0]) {
        if (num1[pos] < num2[pos]) { //需要向高位借位
            num1[pos] += 10;
            --num1[pos + 1];
        }
        res[pos] = num1[pos] - num2[pos];
        ++pos;
    }

    //跳过前导0，判断大于1是考虑结果为0的情况
    while (res[pos] == 0 && pos > 1) --pos;

    for (int i = pos; i >= 1; --i)
        cout << res[i];
    cout << endl;
}

int main()
{
    std::ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    string s1, s2;
    cin >> s1 >> s2;
    //可能存在被减数小于减数的情况
    if (s1.size() < s2.size() || (s1.size() == s2.size() && s1 < s2)) {
        cout << "-";
        std::swap(s1, s2);
    }

    bigNumMinus(s1, s2);

    return 0;
}

洛谷-P2142 高精度减法

这道题看上去和高精度加法类似，但是却布满坑点：

两个字符串相减出现前导0，需要除去比如100-99
前导0并不是所有都需要除去，比如0-0或100-100
两个数相减可能为负，需要在结果前加负号，比较两个数的大小不能直接写成str1 < str2，因为比如38和370，按照字符串的比较规则是38 > 370，所以需要分为位数不同和位数相同两种情况计算。

高精度乘法¶

高精度乘单精度
高精度乘高精度

以上两种可以归结为同一个程序来解决。

//洛谷-P1303 A*B Problem
#include <iostream>
#include <iomanip>
#include <vector>
#include <string>
#include <queue>
#include <set>
#include <map>
#include <algorithm>
#include <cmath>
#include <climits>
#include <cstdio>

using namespace std;

int n = 4005;
vector<int> num1(n), num2(n);
vector<int> res(n);

void init(vector<int> & v, string s)
{
    int len = s.size();
    v[0] = len;
    for (int i = 1; i <= len; ++i)
        v[i] = s[len - i] - '0';
}

void bigNumMultiply(string & s1, string & s2)
{
    init(num1, s1);
    init(num2, s2);

    for (int i = 1; i <= num1[0]; ++i) {
        int extra = 0;
        for (int j = 1; j <= num2[0]; ++j) {
            res[i + j - 1] = num1[i] * num2[j] + extra + res[i + j - 1];
            extra = res[i + j - 1] / 10;
            res[i + j - 1] %= 10;
        }
        res[i + num2[0]] = extra;
    }
    //消除前导0
    int len = num1[0] + num2[0];
    while (res[len] == 0 && len > 1) --len;

    for (int i = len; i >= 1; --i)
        cout << res[i];
    cout << endl;
}

int main()
{
    std::ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    string s1, s2;
    cin >> s1 >> s2;
    bigNumMultiply(s1, s2);

    return 0;
}

这里模拟竖式乘法的时候，始终保持利用数位最小的数的每一位去乘上数位较大的数，最后统一进位。相当于OI Wiki里面“高精度——单精度”的思想。

典型题目：

洛谷-P1303 A*B Problem

需要考虑的问题：

其中一个数是0
其中一个数是1
考虑前导0
两个数中有一个负数
两个数中有两个负数

最后两点在题目里是不需要考虑的，因为题目默认都是给定正数。即使是负数，只需要增加变量来记录符号，影响不大。

高精度乘法可以涉及的知识点：

快速傅里叶变换：洛谷-P1919
Karatsuba乘法

高精度除法¶

主要包含两种方法：

高精度除以单精度
高精度除以高精度

//高精度除以单精度
#include <string>
#include <iostream>

using namespace std;

int main()
{
    string str;
    long long num;
    cin >> str >> num;

    if (str == "0") cout << 0;
    else if (num == 1) cout << str;
    else {
        string res;
        long long extra = 0;
        for (size_t i = 0; i < str.size(); ++i) {
            long long tmp = extra * 10 + (str[i] - '0');
            res += to_string(tmp / num);
            extra = tmp % num;
        }
        int pos = 0;
        while (res[pos] == '0') ++pos;
        res = res.substr(pos);
        cout << res;
    }

    return 0;
}

//高精度除以高精度
#include <string>
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

struct bigNum {
    vector<int> num;
    int len;

    bigNum(int n): len(n) {num.assign(n, 0);}
};

bool compare(const bigNum & a, const bigNum & b)
{
    if (a.len < b.len) return false;
    if (a.len > b.len) return true;
    for (int i = a.len - 1; i >= 0; --i) {
        if (a.num[i] < b.num[i]) return false;
        else if (a.num[i] > b.num[i]) return true;
    }

    return true; //两个数完全一致
}

void subtraction(bigNum & a, const bigNum & minus)
{
    for (int i = 0; i < minus.len; ++i) {
        a.num[i] -= minus.num[i];
        if (a.num[i] < 0) {
            --a.num[i + 1];
            a.num[i] += 10;
        }
    }

    for (int i = a.len - 1; i >= 0; --i) {
        if (a.num[i] != 0) {
            a.len = i + 1; //更新被减数的长度
            return;
        }
    }
    a.len = 0; //恰好整除，a所有位都是0
}

vector<int> divide(bigNum & a, const bigNum & b)
{
    vector<int> res(a.len - b.len + 1, 0);
    for (int i = res.size() - 1; i >= 0; --i) {
        if (a.len == 0) break;
        bigNum minus(b.len + i); //构造被减数
        for (int j = b.len - 1; j >= 0; --j) minus.num[j + i] = b.num[j];

        while (compare(a, minus)) {
            subtraction(a, minus);
            ++res[i];
        }
    }
    reverse(res.begin(), res.end());


    return res;
}

ostream & operator<<(ostream & os, const vector<int> & v)
{
    size_t i = 0;
    while (v[i] == 0) ++i;
    for ( ; i < v.size(); ++i) os << v[i];

    return os;
}

int main()
{
    std::ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    string str1, str2;
    cin >> str1 >> str2;


    if (str1 == "0") cout << 0;
    else if (str2 == "1") cout << str1;
    else if (str1.size() < str2.size() || (str1.size() == str2.size() && str1 < str2)) cout << 0;
    else if (str1 == str2) cout << 1;
    else {
        int length = max(str1.size(), str2.size());
        bigNum a(length), b(length);
        b.len = str2.size();
        //倒序处理，便于后续大数减法的运算
        for (size_t i = 0; i < str1.size(); ++i) a.num[str1.size() - 1 - i] = str1[i] - '0';
        for (size_t i = 0; i < str2.size(); ++i) b.num[str2.size() - 1 - i] = str2[i] - '0';

        cout << divide(a, b);
    }

    return 0;
}

高精度除以高精度的思想其实是高精度减法，可以根据被除数和除数来得出商的最大位数，然后每次在除数后面添加0，构成一个减数，然后去模拟竖式除法。

//输入的两个大数分别位a， b，长度分别是M和N，计算12345/45
//商的最大位数i=M-N+1，即4，设计一个 临时减数，减数后面补齐i-1个0，再进行减法
i=4     12345 < 45000   可以减0个   res[4]=0      减后A：12345
i=3     12345 < 4500    可以减2个   res[3]=2      减后A：3345
i=2     3345  < 450     可以减7个   res[2]=7      减后A：195
i=1     195   < 45      可以减4个   res[1]=4      减后A：15

//res[4]=0，故商的有效位数res[0]--，为3
//结果  商为274，余数15

相当于对竖式除法的模拟。

典型题目：

洛谷-P1480 A/B Problem （高精度除以单精度）
洛谷-P2005 A/B Problem 2 (高精度除以高精度)
SJTU OJ 1016 （高精度除以高精度）

进阶练习：

大整数进制转换¶

大整数845678992357836701转化成16进制，最后两位数字是多少？

将一个30位的大整数转成2进制。

对于这种问题可以有一个简单粗暴的想法，直接写好一个大数bigInteger类，进而进行进制转换的运算，就和正常的内置数据类型运算一样了。

关于进制转换可以单独总结，也可以在这里简单写一下，比如各种进制转换成十进制其实方法都一样，只需要考虑需不需要用到大数运算！从十进制转成其他进制是这里要讨论的问题。一些技巧比如二进制转成八进制或十六进制，如果先转成十进制，再转成八进制或十六进制就浪费时间了，其实可以直接进行转换，思路本质是模拟纸上演算的过程，最后记得倒序输出即可。

//POJ 1220
#include <iostream>
#include <string>
#include <algorithm>

using namespace std;

int charToNum(char ch)
{
    if ('0' <= ch && ch <= '9') return ch - '0';
    if ('A' <= ch && ch <= 'Z') return ch - 'A' + 10;

    return ch - 'a' + 36;
}

char numToChar(int n)
{
    if (0 <= n && n <= 9) return '0' + n;
    if (10 <= n && n <= 35) return 'A' + (n - 10);

    return 'a' + (n - 36);
}

inline bool isAllZero(string & s)
{
    return s.size() == 0 ? true : false;
}

string conversion(string & sequence, int sourceBase, int targetBase)
{
    if (sequence == "0" || sequence == "1") return sequence;
    string res;
    string quotient = sequence; //商数

    while (!isAllZero(quotient)) {
        int extra = 0;
        string tmpStr;
        for (size_t i = 0; i < quotient.size(); ++i) {
            int tmp = extra * sourceBase + charToNum(quotient[i]);
            tmpStr.push_back(numToChar(tmp / targetBase));
            extra = tmp % targetBase;
        }
        res.push_back(numToChar(extra)); //进制转换中的余数

        size_t pos = 0;
        while (tmpStr[pos] == '0') ++pos;
        quotient = tmpStr.substr(pos);
    }
    reverse(res.begin(), res.end());

    return res;
}

int main()
{
    std::ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int caseNum;
    cin >> caseNum;

    while (caseNum--) {
        int sourceBase, targetBase;
        string sequence;
        cin >> sourceBase >> targetBase >> sequence;

        cout << sourceBase << " " << sequence << endl;
        cout << targetBase << " " << conversion(sequence, sourceBase, targetBase) << endl;
        if (caseNum != 0) cout << endl; 
    }

    return 0;
}

掌握一道题目，其他的基本都是类似的了。

典型题目：

POJ 1220 NUMBER BASE CONVERSION
UVA 389 & POJ1546 & HDU 1335 & ZOJ 1334 Basically Speaking（进制转换）
POJ 2196 & HDU 1197 Specialized Four-Digit Numbers
POJ 1331 Multiply
洛谷P1015 回文数（进制转换+高精度加法）
POJ 2330 进制转换