【算法】高精度（string实现）

模板来自：【C++/string】 大数高精度运算模板

加法

string add(string a, string b)
{
    string ans;
    /* 翻转两个数字字符串，使得后面的for循环从个位开始相加 */
    reverse(a.begin(), a.end());
    reverse(b.begin(), b.end());
    /* 初次补0，保证最高位都是‘0’ */
    a.push_back('0');
    b.push_back('0');
    if(a.size() < b.size()) swap(a, b);
    /* 短的字符串高位补‘0’，使两字符串位数相等 */
    while(b.size() < a.size()) b.push_back('0');
    /* 数组c：存放每位相加后的结果  k：字符串补‘0’后的位数 */
    int c[1000]={0}, k = a.size();
    /* 从个位开始，模拟加法 */
    for(int i = 0; i < a.size(); i++){
        int sum = c[i] + a[i]-'0' + b[i] - '0';
        c[i] = sum%10;
        c[i+1] += sum/10;
    }
    /* 去除高位零 */
    while(c[k]==0 && k>=0) k--;
    /* 输出 */
    while(k >= 0)
        ans.push_back(c[k--]+'0');
    return ans;
}

减法

string sub(string a, string b)
{
    string ans;
    /* flag：true表示被减数小于减数，结果为负。false表示结果为正 */
    bool flag = false;
    /* 首先判断被减数与减数的大小关系 */
    if(a.size() < b.size() || (a.size()==b.size() && a < b)){
        swap(a, b);
        flag = true;    
    }
    reverse(a.begin(), a.end());
    reverse(b.begin(), b.end());
    /* 初次补0，保证最高位都是‘0’ */
    a.push_back('0');  b.push_back('0');
    if(a.size() < b.size()) swap(a, b);
    /* 短的字符串高位补‘0’，使两字符串位数相等 */
    while(b.size() < a.size()) b.push_back('0');
    int c[1000]={0}, k = a.size();
    /* 从个位开始，模拟减法 */
    for(int i = 0; i < a.size(); i++){
        if(a[i] < b[i]) a[i]+=10, a[i+1]--;
        c[i] = a[i] - b[i];
    }
    /* 去除高位‘0’ */
    while(c[k]==0 && k>=0) k--;
    /* 输出 */
    if(flag) ans.push_back('-');
    while(k >= 0)
        ans.push_back(c[k--]+'0');
    return ans;
}

乘法

string mcl(string a, string b)
{
    string ans;
    reverse(a.begin(), a.end());
    reverse(b.begin(), b.end());
    /* k：ans字符串可能的最大位数 */
    int c[1000]={0}, k = a.size()+b.size()+1;
    /* 从个位开始，模拟乘法：a的每一位乘以b的每一位 */
    for(int i = 0; i < a.size(); i++)
        for(int j = 0; j < b.size(); j++){
            c[i+j] += (a[i]-'0')*(b[j]-'0');  /* c[i+j]暂存初步乘的结果 */
            c[i+j+1] += c[i+j]/10;   /* 进位 */
            c[i+j] %= 10;       /* c[i+j]保留个位 */
        }
    /* 去除高位‘0’ */
    while(c[k]==0 && k>=0) k--;
    /* 输出 */
    while(k >= 0)
        ans.push_back(c[k--]+'0');
    return ans;
}

除法

string div(string a, long long b)
{
	string ans;
	/* rest：存储余数 */
    int c[256] = {0}, rest = 0;
    /* 从最高位开始，模拟除法 */
    for(int i = 0; i < a.size(); i++){
        rest = 10*rest + a[i] - '0';
        c[i] = rest / b;
        rest %= b;
    }
    // 处理计算结果
    int k = 0;
    /* 去除高位‘0’，k最大不能超过a.size()-1，因为商最少也会有1位 */
    while(c[k] == 0 && k < a.size()-1)
        k++;
    for(int i = k; i < a.size(); i++)
        ans.push_back(c[i]+'0');
    return ans;
}