前言
简介：涉及高精度的加减乘除，题目源于洛谷
建议大家先自行尝试解题，同时阿鑫的水平不高，所以题解也通常并不算好，建议大家可以在洛谷相关题目的题解处查看其他大佬的题解，阿鑫的题解简单看看就好。
本章难度不是很大，所以解释也很少，自行模拟理解即可。
高精度（初级：两位数皆为正整数）
高精度：用于处理数字特别大的计算。
思路：对于这种大数据的，可以采用字符串来存，再通过自行模拟运算即可以得出答案，注释如果不太好理解的话，可以尝试随便挑两个数字（最好长度不一），拿出纸笔，自行模拟代码运行，便会发现其实就是模拟运算。
高精度加法
题目描述
高精度加法，相当于a+b problem，不用考虑负数.
输入格式
分两行输入 。a,b ≤ 10500
输出格式
输出只有一行，代表a+b的值
输入输出样例
输入
1
1
输出
2
输入
1001
9099
输出
10100
两种写法的思路其实并无大区别，只是写法1是在传入参数时将长度长的传入函数的a，而写法2则是巧妙的利用了一下不需要的思路使得题目难度加大一点点（那为什么还要给出呢？因为阿鑫最刚开始写的就是写法2，删了可惜）。
完整代码1
//用时：16ms(O2优化:16ms) 内存：808.00KB
#include <bits/stdc++.h>
using namespace std;
string HighPrecisionAddition(string a,string b){
int i;
//判断哪一个长度更长，更长的当a
if(a.length()<b.length()) swap(a,b);
reverse(a.begin(),a.end()); //反转字符串方便计算,下同
reverse(b.begin(),b.end());
b.append(a.length()-b.length(),'0'); //对长度短的b末尾补0
string sum(a.length()+1,'0'); //初始化sum
for(i=0;i<a.length();i++){
sum[i+1]=(sum[i]+a[i]+b[i]-3*'0')/10+'0'; //模拟加法的进位
sum[i]=(sum[i]+a[i]+b[i]-3*'0')%10+'0'; //模拟加法
}
reverse(sum.begin(),sum.end()); //反转后才是正确顺序
//去除前面多余的0,同时保证不会全删掉（可以输出 0）
while(sum[0]=='0'&&sum.length()>1) sum.erase(sum.begin());
return sum;
}
int main()
{
string a,b;
cin>>a>>b;
cout<<HighPrecisionAddition(a,b)<<endl;
return 0;
}
完整代码2
//用时：16ms(O2优化:16ms) 内存：808.00KB
#include <bits/stdc++.h>
using namespace std;
string HighPrecisionAddition(string a,string b){
string x[2]={a,b}; //x[0]等于a,x[1]=b
int i,ln=x[0].length()<x[1].length();
//如果x[0]长度小于x[1]则ln=1,否则ln=0,即ln等于长度更长的下标
reverse(x[0].begin(),x[0].end()); //反转字符串方便计算,下同
reverse(x[1].begin(),x[1].end());
x[!ln].append(x[ln].length()-x[!ln].length(),'0'); //对长度短的末尾补0
string sum(x[ln].length()+1,'0'); //初始化sum
for(i=0;i<x[ln].length();i++){
sum[i+1]=(sum[i]+x[ln][i]+x[!ln][i]-3*'0')/10+'0'; //模拟加法的进位
sum[i]=(sum[i]+x[ln][i]+x[!ln][i]-3*'0')%10+'0'; //模拟加法
}
reverse(sum.begin(),sum.end()); //反转后才是正确顺序
//去除前面多余的0,同时保证不会全删掉（可以输出 0）
while(sum[0]=='0'&&sum.length()>1) sum.erase(sum.begin());
return sum;
}
int main()
{
string a,b;
cin>>a>>b; //按题意输入
cout<<HighPrecisionAddition(a,b)<<endl; //按题意输出
return 0;
}
高精度减法
题目描述
高精度减法。
输入格式
两个整数 a,b（第二个可能比第一个大）。
输出格式
结果（是负数要输出负号）。
输入输出样例
输入
2
1
输出
1
说明/提示
• 20% 数据 a,b 在 long long 范围内；
• 100% 数据 0 < a,b ≤ 1010086
减法思路也差不多，思路请看注释。
ac题解
//用时：36ms(O2优化:38ms) 内存：808.00KB
#include <bits/stdc++.h>
using namespace std;
string highPrecisionSubtraction(string a,string b){
string ans;
bool flag=false; //判断是否为负数
if(a.length()<b.length()||(a.length()==b.length()&&a<b)){
flag=true;
swap(a,b); //讲大的数字放到a里面,小的放在b
}
reverse(a.begin(),a.end()); //反转字符串方便计算,下同
reverse(b.begin(),b.end());
b.append(a.length()-b.length(),'0');//小的数字前面补0
for(int i=0;i<a.length();i++){
if(a[i]<b[i]){ //如果不够减，向前面借1
ans+=a[i]-b[i]+10+'0';
a[i+1]--;
}else{ //够减直接减
ans+=a[i]-b[i]+'0';
}
}
reverse(ans.begin(),ans.end());
//去除前面多余的0,同时保证不会全删掉（可以输出答案为 0）
while(ans[0]=='0'&&ans.length()>1) ans.erase(ans.begin());
if(flag) ans.insert(ans.begin(),'-');
return ans;
}
int main()
{
string a,b;
cin>>a>>b;
cout<<highPrecisionSubtraction(a,b)<<endl;
return 0;
}
高精度乘法
高精乘低精
该题没找到合适题目，故只提供代码（当然也可以用下面的高精乘高精的例题测试，直接long long*long long应该是40分，用高精乘低精应该是60分）。
思路
模拟乘法竖式运算。
参考代码
#include <bits/stdc++.h>
using namespace std;
//高精度乘低精度
string highPrecisionMultiplication(string a,long long b){
string ans;
long long t=0;
reverse(a.begin(),a.end()); //反转字符串方便计算,下同
//模拟乘法竖式运算
for(int i=0;i<a.length();i++){
t+=(a[i]-'0')*b;
ans+=t%10+'0';
t/=10;
}
while(t){
ans+=t%10+'0';
t/=10;
}
reverse(ans.begin(),ans.end());
//去除前面多余的0,同时保证不会全删掉（可以输出 0）
while(ans[0]=='0'&&ans.length()>1) ans.erase(ans.begin());
return ans;
}
int main()
{
string a;
long long b;
cin>>a>>b;
cout<<highPrecisionMultiplication(a,b)<<endl;
return 0;
}
高精乘高精
题目描述
求两数的积。
输入格式
两行，两个整数。
输出格式
一行一个整数表示乘积。
输入输出样例
输入
1
2
输出
2
说明/提示
• 每个数字不超过 102000，需用高精。
思路
模拟乘法竖式运算。
ac题解
//用时：44ms(O2优化:22ms) 内存：856.00KB
#include <bits/stdc++.h>
using namespace std;
string highPrecisionMultiplication(string a,string b){
string ans;
reverse(a.begin(),a.end()); //反转字符串方便计算,下同
reverse(b.begin(),b.end());
for(int i=0;i<a.length();i++){
int t=0,tt=0;
for(int j=0;j<b.length();j++){
if(ans[i+j]) tt=ans[i+j]-'0';
else tt=0;
if(ans[i+j]) ans[i+j]=((a[i]-'0')*(b[j]-'0')+t+tt)%10+'0';
else ans+=((a[i]-'0')*(b[j]-'0')+t+tt)%10+'0';
t=((a[i]-'0')*(b[j]-'0')+tt+t)/10;
}
if(t>0) ans+='0'+t;
}
reverse(ans.begin(),ans.end());
//去除前面多余的0,同时保证不会全删掉（可以输出 0）
while(ans[0]=='0'&&ans.length()>1) ans.erase(ans.begin());
return ans;
}
int main()
{
string a,b;
cin>>a>>b;
cout<<highPrecisionMultiplication(a,b)<<endl;
return 0;
}
高精度除法
高精度除低精
题目描述
输入两个整数 a,b，输出它们的商。
输入格式
两行，第一行是被除数，第二行是除数。
输出格式
一行，商的整数部分。
输入输出样例
输入
10
2
输出
5
说明/提示
0≤a≤105000，1≤b≤109。
解题思路：
高精除低精的难度不大，就是模拟除法（废话），故不多做解释，看着代码模拟下就可以理解了。
ac题解
//时间：23ms(O2:21ms) 内存：852.00KB
#include <bits/stdc++.h>
using namespace std;
string highPrecisionDivision(string a,int b){
string ans="";
long long t=0;
int flag=0; //flag==1时开始记录答案，因为前面都不够除，无需补零
for(int i=0;i<a.length();i++){
t=t*10+(a[i]-'0');
if(t/b)flag=1;
if(flag){
ans+=(t/b)+'0';
}
t%=b;
}
if(ans!="")return ans;
else return "0";
}
int main()
{
string a;
int b;
cin>>a>>b;
cout<<highPrecisionDivision(a,b)<<endl;
return 0;
}
高精度除高精
题目背景
为了让大家紧张的心情放松一下，这一题题是一道非常简单的题目。
题目描述
给出正整数N和M，请你计算N div M（N/M的下取整）。
输入格式
两行，两个正整数，N和M。
输出格式
一行，一个整数，表示N div M。
输入输出样例
输入
1000
333
输出
3
说明/提示
• 对于60%的数据：N，M ≤ 750!，答案≤ 7!。
• 对于100%的数据：N，M ≤ 6250!，答案≤ 13!。
请注意：上面的两句话并不是感叹句，而是陈述句。标点符号使用没有错误。
这题较前面几题稍稍难些，所以多写点思路讲解。
解题思路：
该题阿鑫的思路为用减法实现,一直减到无法再减（当然纯暴力是不行的，会有部分TLE）
用例子讲解或许会好一点：
假设 a：2022 b:59
首先比较两数长度之差 dis = 4-2 = 2
对 b 补 dis-1个0，并用 d 暂时保存，d = b 10dis-1 = 59 10 = 590
（为何是dis-1？ 如果 除数 补dis个零的话可能会大于 被除数 ）
用 c 暂时保存 a (避免减多了), 对 c 不断减 d，每减一个d 相当于减去 10dis-1个b(用 t 保存10dis-1，注意 t 如果小于1，将 t=1)，故 ans 每次加上 t。
此处c=a=2022， t=10dis-1=10
（为何 t 如果小于1，将 t=1？ 如果两位数位数相等如 9 3，那么 t =10dis-1 = 10-1= 0.1,而9每减去3，ans应该+1而不是+0.1，故 t 如果小于1，将 t=1 ）
不断减至无法再减去（即 c - d < 0），如果可以减，则更新 a = c，ans+=t，c-=d。
c=c-d=2022 - 590 = 1432
c=1432>0 => a=1432 ，ans=ans+10=10 ， c=c-d=1432 - 590=842
c=842>0 => a=842 ， ans=ans+10=20 ， c=c-d=842 - 590=252
c=252>0 => a=252 ，ans=ans+10=30 ，c=c-d=252-590=-338
c=-338<0结束本轮
重复上述步骤开启新一轮(此时a=252，b=59，dis=1 ，t=1 ，c=a=252 ，d=59)
c=c-d=252 - 59 = 193
c=1432>0 => a=193 ，ans=ans+1=31 ， c=c-d=193 - 59=134
c=134>0 => a=134 ， ans=ans+1=32 ， c=c-d=134 - 59=75
c=75>0 => a=75 ， ans=ans+1=33 ， c=c-d=75 - 59=16
c=16>0 => a=16 ，ans=ans+1=34 ，c=c-d=16-59=-43
c=-43<0结束本轮
此时a=16,b=59,a<b结束除法，返回答案ans=34
（注：由于本题输出答案的特殊性(答案≤ 13!，long long可以存下)，所以只用了高精度减法，否则用上述思路的加法乘法也应改为高精度加法乘法）
ac题解
//用时：544ms(O2优化:147ms) 内存：808.00KB
#include <bits/stdc++.h>
using namespace std;
//高精度减法(不做赘述)
string highPrecisionSubtraction(string a,string b){
string ans;
bool flag=false;
if(a.length()<b.length()||(a.length()==b.length()&&a<b)){
flag=true;
swap(a,b);
}
reverse(a.begin(),a.end());
reverse(b.begin(),b.end());
b.append(a.length()-b.length(),'0');
for(int i=0;i<a.length();i++){
if(a[i]<b[i]){
ans+=a[i]-b[i]+10+'0';
a[i+1]--;
}else{
ans+=a[i]-b[i]+'0';
}
}
reverse(ans.begin(),ans.end());
while(ans[0]=='0'&&ans.length()>1) ans.erase(ans.begin());
if(flag) ans.insert(ans.begin(),'-');
return ans;
}
//高精度除法
long long highPrecisionDivision (string a,string b){
string c=a,d=b;
long long ans=0,dis=0,t;
while(1){
//如果一个b都减不了，则跳出
c=highPrecisionSubtraction(a,b);
if(c[0]=='-') break;
dis=a.length()-b.length(); //计算两数 位数差
d=b;
for(int i=0;i<dis-1;i++){ //为其补零
d+='0';
}
c=highPrecisionSubtraction(a,d);
t=pow(10,dis-1); //t存储每次减去多少个b
if(t<1) t=1; //很重要，因为当两数位数相等时,dis-1=-1,t=pow(10,-1)=0.1;
while(c[0]!='-'){ //减到不能减
a=c;
ans+=t;
c=highPrecisionSubtraction(c,d);
}
}
return ans;
}
int main()
{
string n,m;
cin>>n>>m;
cout<<highPrecisionDivision(n,m)<<endl;
return 0;
}
补充
阿鑫在上面也说过，可以long long是因为题目的特殊性（答案≤ 13!），但如果答案long long存不下，就也应该用string存储，当然其实要改的地方并不多。下面给出完整代码。
另一ac题解
//时间：563ms (O2:148ms) 内存：808.00KB
#include <bits/stdc++.h>
using namespace std;
//高精度加法(不做赘述)
string HighPrecisionAddition(string a,string b){
int i;
//判断哪一个长度更长，更长的当a
if(a.length()<b.length()) swap(a,b);
reverse(a.begin(),a.end()); //反转字符串方便计算,下同
reverse(b.begin(),b.end());
b.append(a.length()-b.length(),'0'); //对长度短的b末尾补0
string sum(a.length()+1,'0'); //初始化sum
for(i=0;i<a.length();i++){
sum[i+1]=(sum[i]+a[i]+b[i]-3*'0')/10+'0'; //模拟加法的进位
sum[i]=(sum[i]+a[i]+b[i]-3*'0')%10+'0'; //模拟加法
}
reverse(sum.begin(),sum.end()); //反转后才是正确顺序
//去除前面多余的0,同时保证不会全删掉（可以输出 0）
while(sum[0]=='0'&&sum.length()>1) sum.erase(sum.begin());
return sum;
}
//高精度减法(不做赘述)
string highPrecisionSubtraction(string a,string b){
string ans;
bool flag=false;
if(a.length()<b.length()||(a.length()==b.length()&&a<b)){
flag=true;
swap(a,b);
}
reverse(a.begin(),a.end());
reverse(b.begin(),b.end());
b.append(a.length()-b.length(),'0');
for(int i=0;i<a.length();i++){
if(a[i]<b[i]){
ans+=a[i]-b[i]+10+'0';
a[i+1]--;
}else{
ans+=a[i]-b[i]+'0';
}
}
reverse(ans.begin(),ans.end());
while(ans[0]=='0'&&ans.length()>1) ans.erase(ans.begin());
if(flag) ans.insert(ans.begin(),'-');
return ans;
}
//高精度乘法(不做赘述)
string highPrecisionMultiplication(string a,string b){
string ans;
reverse(a.begin(),a.end()); //反转字符串方便计算,下同
reverse(b.begin(),b.end());
for(int i=0;i<a.length();i++){
int t=0,tt=0;
for(int j=0;j<b.length();j++){
if(ans[i+j]) tt=ans[i+j]-'0';
else tt=0;
if(ans[i+j]) ans[i+j]=((a[i]-'0')*(b[j]-'0')+t+tt)%10+'0';
else ans+=((a[i]-'0')*(b[j]-'0')+t+tt)%10+'0';
t=((a[i]-'0')*(b[j]-'0')+tt+t)/10;
}
if(t>0) ans+='0'+t;
}
reverse(ans.begin(),ans.end());
//去除前面多余的0,同时保证不会全删掉（可以输出 0）
while(ans[0]=='0'&&ans.length()>1) ans.erase(ans.begin());
return ans;
}
//高精度除法
string highPrecisionDivision (string a,string b){
if(a=="0") return "0";
if(b=="0") return "无意义";
string ans="",t,c=a,d=b;
long long dis=0;
while(1){
//如果一个b都减不了，则跳出
c=highPrecisionSubtraction(a,b);
if(c[0]=='-') break;
dis=a.length()-b.length(); //计算两数 位数差
d=b;
for(int i=0;i<dis-1;i++){ //为其补零
d+='0';
}
c=highPrecisionSubtraction(a,d);
t="1";//t存储每次减去多少个b
for(int i=1;i<=dis-1;i++){
t+="0";
}
while(c[0]!='-'){ //减到不能减
a=c;
ans=HighPrecisionAddition(ans,t);
c=highPrecisionSubtraction(c,d);
}
}
if(ans=="")ans="0";
return ans;
}
int main()
{
string n,m;
cin>>n>>m;
cout<<highPrecisionDivision(n,m)<<endl;
return 0;
}
高精度取余
思路：
会了高精度除法，其实也就会取余了（要改的地方就一处）,故不多做讲解，也只给出部分代码。
//高精度取余（只给出关键代码）
string highPrecisionDivision (string a,string b){
if(a=="0") return "0";
if(b=="0") return "无意义";
string ans="",t,c=a,d=b;
long long dis=0;
while(1){
//如果一个b都减不了，则跳出
c=highPrecisionSubtraction(a,b);
if(c[0]=='-') break;
dis=a.length()-b.length(); //计算两数 位数差
d=b;
for(int i=0;i<dis-1;i++){ //为其补零
d+='0';
}
c=highPrecisionSubtraction(a,d);
t="1";//t存储每次减去多少个b
for(int i=1;i<=dis-1;i++){
t+="0";
}
while(c[0]!='-'){ //减到不能减
a=c;
ans=HighPrecisionAddition(ans,t);
c=highPrecisionSubtraction(c,d);
}
}
/*高精度除以高精度，修改了这一处，则变为取余
if(ans=="")ans="0";
return ans;*/
return a;//aji
}