高精度运算

高精度加减乘除，用于处理大整数运算，不但远超INT型上界，也可以远超 Long Long 型上界。

大整数的保存方法

使用vector从个位开始往高位存。

正整数高精度加法

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

void set_val(const string& val, vector<int>& vals)
{
    int m = val.size();
    for(int i = m - 1; i >= 0; --i)
        vals.push_back(val[i] - '0');
}

void sum(const vector<int>& a, const vector<int>& b, vector<int>& res)
{
    int m = a.size(), n = b.size(), t = 0;//t为进位符号
    for(int i = 0; i < m || i < n; ++i)
    {
        if(i < m) t += a[i];
        if(i < n) t += b[i];
        res.push_back(t % 10);
        t /= 10;
    }
    if(t) res.push_back(t);
}

int main()
{
    string val1, val2;
    cin >> val1 >>val2;
    vector<int> a, b, res;
    set_val(val1, a), set_val(val2, b);
    sum(a, b, res);
    for(int i = res.size() - 1; i >= 0; --i)
        cout << res[i];
    return 0;
}

正整数高精度减法

考虑结果为负数的情况

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

void set_val(const string& val, vector<int>& vals)
{
    int m = val.size();
    for(int i = m - 1; i >= 0; --i)
        vals.push_back(val[i] - '0');
}

bool cmp(const vector<int>& a, const vector<int>& b)
{
    int m = a.size(), n = b.size();
    if(m != n) return m < n;
    for(int i = m - 1; i >= 0; --i)
    {
        if(a[i] > b[i]) return false;
        else if(a[i] == b[i]) continue;
        else return true;
    }
    return false;
}

void sub(const vector<int>& a, const vector<int>& b, vector<int>& res)
{
    int m = a.size(), n = b.size(), t = 0;
    for(int k = 0; k < m || k < n; ++k)
    {
        int i = 0, j = 0;
        if(k < m) i = a[k];
        if(k < n) j = b[k];
        t = i - j - t;
        res.push_back((t + 10) % 10);
        t = 1 - (t + 10) / 10;//判断当前位是否需要借位
    }
    while(res.size() > 1 && res.back() == 0)
        res.pop_back();
}

int main()
{
    string val1, val2;
    cin >> val1 >> val2;
    vector<int> a, b, res;
    set_val(val1, a), set_val(val2, b);
    bool isminus = cmp(a, b);
    if(isminus) sub(b, a, res);
    else sub(a, b, res);
    if(isminus) cout << "-";
    for(int i = res.size() - 1; i >= 0; --i)
        cout << res[i];
    return 0;
}

高精度乘法（大数乘以一个较小数）

其实两个大数也是可以做的。(LeetCode43.字符串相乘)

这种题目更为简单。

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

void set_val(const string& val, vector<int>& vals)
{
    int m = val.size();
    for(int i = m - 1; i >= 0; --i)
        vals.push_back(val[i] - '0');
}

void mul(const vector<int>& a, int b, vector<int>& res)
{
    int m = a.size(), t = 0;
    for(int i = 0; i < m; ++i)
    {
        t += a[i] * b;
        res.push_back(t % 10);
        t /= 10;
    }
    if(t) res.push_back(t);
    while(res.size() > 1 && res.back() == 0)
        res.pop_back();
}

int main()
{
    string val1;
    int b;
    cin >> val1 >> b;
    vector<int> a, res;
    set_val(val1, a);
    mul(a, b, res);
    for(int i = res.size() - 1; i >= 0; --i)
        cout << res[i];
    return 0;
}

高精度除法(一个大数除以一个较小数并求余数)

这个就比较麻烦了。要明确除法是要从高位开始往低位运算的。

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

void set_val(const string& val, vector<int>& vals)
{
    int m = val.size();
    for(int i = m - 1; i >= 0; --i)
        vals.push_back(val[i] - '0');
}

void div(const vector<int>& a, int b, vector<int>& res, int& mod)
{
	int m = a.size(), t = 0;
	for(int i = m; i >= 0; --i)
	{
		if((t * 10 + a[i]) / b)//够除
		{
			res.push_back((t * 10 + a[i]) / b);
			t = (10 * t + a[i]) % b;
		}
		else //不够除，要借一位
		{
			res.push_back(0);
			t = t * 10 + a[i];
		}
	}
	mod = t;
	reverse(res.begin(), res.end());//注意翻转
	while(res.size() > 1 && res.back() == 0)
		res.pop_back();
}

int main()
{
	string val1;
	int b, mod;
	cin >> val1 >> b;
	vector<int> a, res;
	set_val(val1, a);
	div(a, b, res, mod);
	for(int i = res.size() - 1; i >= 0; --i)
		cout << res[i];
	cout << endl;
	cout << mod << endl;
	return 0;
}