【算法】高精度（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;
}