高精度加减乘除

ps:感觉csdn的写文章功能有点小毛病，本文所有的竖式都错位了…我人傻了，还是改不了的那种错位，罢了罢了，凑合着看看吧555

1.数据范围

（1）A+B（两个大整数相加）：

​ A和B的位数是10⁶

（2）A-B（两个大整数相减）：

​ A和B的位数是10⁶

（3）A×b（一个大整数乘一个小整数）：

​ A的位数：len(A)<=10⁶

​ b的数值<=10⁹（也有可能是b<=10000,总之，b特别小，A特别大）

（4) A÷b ：

​ 求商和余

2.大整数存储（大整数在c++中如何存储？？？）

答：把大整数的每一位存到数组里面去，用数组来存，数组里的每一位存一个数字

例：有一个九位的大整数：123456789，要把它的每一位都存到数组里面去。假设有一个数组的下标分别是0、1、2、3、4、5、6、7、8，那么在这里，应该要把数组的最低位存个位的数字，数组的最高位存数字的最高位上的数字，即数组的第0位是9，数组的第1位是8，数组的第2位是7，数组的第3位是6，数组的第4位是5，数组的第5位是4，数组的第6位是3，数组的第7位是2，数组的第8位是1。

（因为做加减乘除的时候可能需要进位，如果进位的话，就需要我们在高位上补上一个数，那么如果要在高位补上一个数的话，那么在数组的末尾补上一个数是最容易的，如果想在数组的开头补上一个数的话，那就需要把整个数组全部往后平移一位，就会比较麻烦，所以我们在存的时候，就会把个位存在下标是0的数组里，以此类推）

3.运算

高精度加法：

算法流程*（模拟人工加法的过程）*

首先先回忆小学时学加法的时候是如何做的？

举例：
1 2 3

​ ＋ 8 9

​ —————

​ 2 1 2

首先先把两个数组的个位相加3+9得12，然后个位写2，进1位，然后是第1个数组的第2位加上第2个数组的第2位再加上进的1位得11，于是十位上写1，再进1位，然后是第一个数组的第3位加上第2个数组的第3位再加上进位就是2，最后结果就是212

因此，目标就是运用代码去模拟上述的过程

假设，已经有了两个数组(因为这是反着存储的，所以A₀、B₀存的是个位)

第一个数组 A₃ A₂ A₁ A₀

第二个数组 ＋ B₂ B₁ B₀

​ ————————————————

​ C₀

首先算一下A₀+B₀，如果结果大于10，则进1位，如果小于10，则不进位;C₀=（A₀+B₀）%10

第2位就是A₁+B₁+进位，判断结果是否大于10，大于10就进位，小于10则不进位…以此类推

所以每次算每一位的时候，实际上是三个数相加A_i+B_i+t(t表示上一位的进位，上一位如果没有进位的话，t就是0，如果有进位的话，t就是1)

如果A_i或B_i不存在的话，把那一位看成0就行，最好再看一下t有没有进位，若有进位，再补上一个1

AC代码：

#include <iostream>
#include <vector>
#include <cstdio>using namespace std;//若返回值是C的话，C=A+B 
vector<int> add(vector<int> &A,vector<int> &B)//加&可以提高效率，不加&的话，会导致程序运行时会把整个数组copy一遍 
{//这个函数是计算用数组表示的大整数A+用数组表示的大整数Bvector<int> C;//返回值是一个用数组表示的整数C，定义一下int t=0;//进位，刚开始的时候进位相当于0for(int i=0;i<A.size()||i<B.size();i++)//用数组表示整数的时候是倒着表示的，A.size()表示返回数组A的实际长度{if(i<A.size())//若i没有超过数组A的实际长度的话 {t+=A[i];//有A[i]就加A[i]}if(i<B.size())//如果i没有超过数组B的实际长度的话{t+=B[i];//有B[i]就加B[i]}//上面两个if语句执行完以后，t里面存的就是A[i]+B[i]+t(进位)C.push_back(t%10);//把(t%10)插到vector C的尾部t/=10; //判断是否要进位，大于10的话，t就是1，小于10的话，t就是0}if(t){C.push_back(1);//判断最高位有没有进位，如果有进位的话就是1，就要在结果前补上一个1}return C;
}
int main()
{string a,b;//因为太长了，所以要用字符串读入vector<int> A,B;//存到vector里面去cin>>a>>b;//读入两个整数a和b，举例：此时a的形式应该是为"123456" //然后将a这个字符串的这个整数的每一位扣出来放到vector里面去（第一步：大整数存储）for(int i=a.size()-1;i>=0;i--) //因为是逆序，所以需要从前往后遍历每一位 {A.push_back(a[i]-'0');//这里需要存的是数字，而我们这里是字母的数字，要变成整数就得减去0，减去一个偏移量 }//如果说a是"123456",那么A里存的就是A=[6,5,4,3,2,1] for(int i=b.size()-1;i>=0;i--){B.push_back(b[i]-'0');//因为string默认存储的是字符串，所以要减去'0'才能得到真实数值} vector<int> C=add(A,B);for(int i=C.size()-1;i>=0;i--){printf("%d",C[i]);}return 0;
}

高精度减法：

注：加减乘除四种运算里的大整数存储都是一致的，因为在一道题里面，可能最终的答案是很大的一个数，那么在我们最终把答案算出来的这个过程可能会包含加减乘除四种运算，则必须使这几种运算同时进行，那么它们的大整数的存储的格式就必须一致

算法流程

举例： 1 2 3

​ － 8 9

——————————

​ 4

首先先看个位，3-9不够减，则需要借1位，答案是4，那么2变成了1，再用1-8不够减，再借1位，11-8得3，所以最终答案是34

在一般情况下，假设有两个数组（确保A>=B）

第一个数组： A₃ A₂ A₁ A₀

第二个数组： － B₂ B₁ B₀

​ —————————————

​ C₀

首先A₀-B₀，如果不够减，就向前面借1位，然后再加上10…

Ai-Bi-t可以分成2种情况： (1)值>=0，Ai-Bi-t（直接减）

​ (2)值<0，Ai-Bi+10-t

(t是来看上一位有没有借位，t为1，则上一位有借位，t为0，则上一位没有借位)

综上：

做大整数减法A-B的题目时分两步：（1）判断若A>=B的话，则直接计算A-B；（2）若A<B的话，就计算-（B-A）

优点：

保证每次做减法的时候，一定是较大的数减去较小的数，一定不会出现负数的情况，因此，最高位一定不会再往前进位，就会少处理一些边界情况

AC代码：

#include <iostream>
#include <vector>
#include <cstdio>using namespace std;//判断是否有A>=B 
bool cmp(vector<int> &A,vector<int> &B)
{if(A.size()!=B.size())//如果两个数的位数不同 {return A.size()>B.size();//A的位数大的话，A就大；A的位数小的话，A就小 }for(int i=A.size()-1;i>=0;i--){if(A[i]!=B[i]){return A[i]>B[i];}}return true;
}//若返回值是C的话，C=A-B 
vector<int> sub(vector<int> &A,vector<int> &B)
{vector<int> C;//定义一个答案for(int i=0,t=0;i<A.size();i++)//从前往后做{t=A[i]-t;if(i<B.size())//判断B是不是存在，因为B的位数可能比A的位数要少 {t-=B[i];//若存在，再进行相减}C.push_back((t+10)%10);//因为t的范围一定是个位数，那么如果t>0，则这步运算结果还是t，如果t<0,那就t+10...if(t<0)//需要借位{t=1;}else//反之，不需要{t=0;}}while(C.size()>1&&C.back()==0)//去掉前导0{C.pop_back();}return C;}
int main()
{string a,b;vector<int> A,B;cin>>a>>b;for(int i=a.size()-1;i>=0;i--)  {A.push_back(a[i]-'0'); }for(int i=b.size()-1;i>=0;i--){B.push_back(b[i]-'0');} if(cmp(A,B))//如果A>B,则直接计算 {vector<int> C=sub(A,B);//A-Bfor(int i=C.size()-1;i>=0;i--){printf("%d",C[i]);}}else//反之 {vector<int> C=sub(B,A);//B-Aprintf("-");//先输出一个负号 for(int i=C.size()-1;i>=0;i--){printf("%d",C[i]);}}return 0;
}

高精度乘法：

举例： 1 2 3

​ × 1 2

​ —————————(进位t₃ t₂ t₁)

​ C₃ C₂ C₁ C₀

C₀=(3×12)%10=6

t₁=$\frac{3\times n}{10}$=3

C₁=(2×n+t₁)%10=7

t₂=2

C₂=(1×n+2)%10=4

t₃=1

C₃=1

最终结果：1476

假设有两个数组

第一个数组： A₅ A₄ A₃ A₂ A₁ A₀

第二个数组： × b

​ ————————————————————

首先结果的个位应该是A₀×b%10，那么需要进位的数字应该是[$\frac{A0\times b}{10}$]，那么第二位上的数字就应该是(A₁×b+t)%t，那么它需要进位的数字就是[$\frac{A1\times b+t}{10}$]

高精度×低精度

AC代码：

#include <iostream>
#include <vector>
#include <cstdio>using namespace std;//C=A*b
vector<int> mul(vector<int> &A,int b)
{vector<int> C;int t=0;//进位 for(int i=0;i<A.size()||t;i++){if(i<A.size())//若A没有遍历完 {t+=A[i]*b;}C.push_back(t%10);t/=10;//进位 }while(t){C.push_back(t%10);t/=10;}while(C.size()>1&&C.back()==0){C.pop_back();}return C;
}
int main()
{string a;//A很长，所以需要用字符串存 int b;//B很短，所以用int就可以了 cin>>a>>b;vector<int> A;for(int i=a.size()-1;i>=0;i--){A.push_back(a[i]-'0'); }vector<int> C=mul(A,b);for(int i=C.size()-1;i>=0;i--){printf("%d",C[i]);}return 0;
}

高精度×高精度

AC代码：

#include <iostream>
#include <vector>
#include <cstdio>using namespace std;//C=A*b
vector<int> mul(vector<int> &A,vector<int> &B)
{vector<int> C(A.size()+B.size(),0);//这里把C的大小设置成乘法结果可能的大小，并初始化为0；两个大数相乘，大小是两个大数位数之和减一或者就是两个大sfor(int i=0;i<A.size();i++){for(int j=0;j<B.size();j++){C[i+j]+=A[i]*B[j];}}int t=0;//进位 for(int i=0;i<C.size();i++)//i=C.size()-1时t一定小于10 {t+=C[i];C[i]=t%10;t/=10;}while(C.size()>1&&C.back()==0)//必须要去前导0，因为最高位很可能是0 {C.pop_back();}return C;
}
int main()
{string a,b;cin>>a>>b;vector<int> A,B;for(int i=a.size()-1;i>=0;i--){A.push_back(a[i]-'0'); }for(int i=b.size()-1;i>=0;i--){B.push_back(b[i]-'0');}vector<int> C=mul(A,B);for(int i=C.size()-1;i>=0;i--){printf("%d",C[i]);}return 0;
}

高精度除法：

高精度÷低精度

AC代码：

#include <iostream>
#include <vector>
#include <cstdio>
#include <algorithm>using namespace std;//A/b,商是C，余数是r 
vector<int> div(vector<int> &A, int b, int &r)//r是引用
{vector<int> C;//C是商r=0;for(int i=A.size()-1;i>=0;i--){r=r*10+A[i];C.push_back(r/b);r%=b;}reverse(C.begin(),C.end());while(C.size()>1&&C.back()==0)//可能存在前导0{C.pop_back();}return C;
}
int main()
{string a;int b;cin>>a>>b;vector<int> A;for(int i=a.size()-1;i>=0;i--){A.push_back(a[i]-'0'); }int r;vector<int> C=div(A,b,r);for(int i=C.size()-1;i>=0;i--){printf("%d",C[i]);}cout<<endl<<r<<endl;return 0;
}

高精度÷高精度

AC代码：

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstdio>using namespace std;bool cmp(vector<int> &A, vector<int> &B)
{if(A.size()!=B.size()){return A.size()>B.size();}for(int i=A.size()-1;i>=0;i--){if(A[i]!=B[i]){return A[i]>B[i];}}return true;
}vector<int> sub(vector<int> &A, vector<int> &B)
{vector<int> C;int t=0;for(int i=0;i<A.size()||t;i++){t=A[i]-t;if(i<B.size()){t-=B[i];}C.push_back((t+10)%10);if(t<0){t=1;}else{t=0;}}while(C.size()>1&&C.back()==0){C.pop_back();}return C;
}vector<int> div(vector<int> &A, vector<int> &B, vector<int> &r)
{vector<int> C;int j=B.size();r.assign(A.end()-j,A.end());while(j<=A.size()){int k=0;while(cmp(r,B)){vector<int> s=sub(r,B);r.clear();r.assign(s.begin(),s.end());k++;}C.push_back(k);if(j<A.size()){r.insert(r.begin(),A[A.size()-j-1]);}if(r.size()>1&&r.back()==0){r.pop_back();}j++;}reverse(C.begin(),C.end());while(C.size()>1&&C.back()==0){C.pop_back();}return C;
}int main()
{string a,b;cin>>a>>b;vector<int> A,B,r;for(int i=a.size()-1;i>=0;i--){A.push_back(a[i]-'0');}for(int i=b.size()-1;i>=0;i--){B.push_back(b[i]-'0');}vector<int> C=div(A,B,r);for(int i=C.size()-1;i>=0;i--){printf("%d",C[i]);}cout<<endl;for(int i=r.size()-1;i>=0;i--){printf("%d",r[i]);}return 0;
}