行业知识
算法基础1.2：高精度，前缀和，差分
高精度运算：
只���C++需要高精度的学习，JAVA和python则不需要，因为JAVA是大整数类，没有位数要求，python默认数的范围就是无限大，只有C++没有大整数类。
高精度主要服务于比较大的整数加减乘除，一般来说高精度考四种。
第一种的话是两个比较大的整数相加（a和b的位数大概是10的六次方）。
第二种是两个比较大的整数相减（a和b的位数大概是10的六次方）。
第三种是一个大整数乘上一个小的整数。（大整数的长度小于10的6次方，小的整数小于等于10的9次方，是特别长的一个数。
第四种是a÷b求商和余数是多少，
比如求方案数，n个苹果，选出来若干个。问有多少种选法，答案是二的N次方，当n是1000的时候，一万的时候，那么它总共的位数肯定是3000位，就很长了。
第一个问题：大整数的存储
大整数，在C++里面代码里面是如何表示的？首先会爆掉int变量，用int变量肯定是存不下来的，大多数时候其实是把它的每一位存到数组里面去，，比方说一个大整数是123456789，一共是九位的一个整数，我们会把它的每一位存到数组里面去，存的时候就有一个问题，我们应该是高位在前呢，还是低位在前呢？假设我们有一个数组的下标是从012345678，第0位应该存一还是存九呢？其实第0位应该存九比较好。数组里边分别存的987654321，为什么把个位存到这个数组的第一个数，然后把最高位存到最后一个数呢？主要是因为两个整数相加，乘法或除法的时候，可能会有进位，就需要在高位上补上一个数，数组的话就在最后一个数，在数组的末尾补上一个数是最容易的，在数组的开头，如果想补上一个数，那就需要把整个数组全部往后平移一位啊，比较麻烦。但是如果往末尾添加一个数字的话，就很好加了，就直接往后push back 1个数就可以了，因此我们存的时候，个位是数组中第零个下标是零的，这个位置存个位，下标是一的，这个位置存十位，以此类推。和我们一般的写法是反着的，我们一般写的话会先写高位，但是在数组中会先写低位。加减乘除的大整数存储都一样。主要是因为题目里面最终答案可能是很大的，中间把答案算出来，这个过程可能会包含加减乘除。必须要这几个运算要同时进行，所以整数存储的格式就一致
高精度1.加法
高精度的加法是一个模拟人工加法的过程，与小学加法相同。用代码去模拟相加进位这个过程，假设已有A和B数组，那么A数组的A0是个位，A1是十位，以此类推到A3，B组比方只有三B2B1B0，B0存的是个位。然后我们A和B相加，首先算a0加上b0是多少，如果大于十的话，就进一位，如果小于十的话，就不进位。然后新的个位就是a+b.模十，比方说写成c0，二位再算的时候就是a1加上b1，再加上进位，算一下是不是大于十，如果大于十的话，就进位，如果不大于十的话，就不进位，新十位就是三个数的和模10，求出c1，以此类推。算每一位的时候，实际上是三个数相加，就是Ai+Bi，再加上上一位的进位，比方叫做t，上一位的进位是t，上一位如果没有进位的话t就是零啊，如果有进位的话t就是一。最开始的也可以让t=0，相当于进了一个零。每一位都是这样，如果Ai或者Bi不存在，那么我们就把它看成零。
模板题：
给定两个正整数（不含前导 0），计算它们的和。
输入格式
共两行，每行包含一个整数。
输出格式
共一行，包含所求的和。
数据范围
1≤整数长度≤100000
输入样例：
1223
输出样例：
35
#include
#include //vector 是变长数组，支持随机访问，不支持在任意位置 O(1)插入。为了保证效率，元素的增删一般应该在末尾进行。
using namespace std;
vector add(vector &A, vector &B) //加上引用的目的是为了提高效率，如果不加引用就会把整个数组copy 1遍，如果加上引用就不会拷贝整个数组。
{
if (A.size()
vector C; //C=A+B
int t = 0; //定义进位
for (int i = 0; i
{
t += A[i];
if (i
C.push_back(t % 10);
t /= 10; //t大于10进位，否则不进位
}
if (t) C.push_back(t); //如果最高位还有进位，就在C的最后加上
return C;
}
int main()
{
string a, b; //用字符串读入
vector A, B; //vector a; 相当于一个长度动态变化的 int 数组，vector b[233]; 相 当于第一维长 233，第二位长度动态变化的 int 数组
cin >> a >> b; //a='123456'
for (int i = a.size() - 1; i >= 0; i -- ) A.push_back(a[i] - '0'); //第一步大整数存储，把每一位抠 出来放到vector中去，a.push_back(x) 把元素 x 插入到 vector a 的尾部，A=[6,5,4,3,2,1]
for (int i = b.size() - 1; i >= 0; i -- ) B.push_back(b[i] - '0');//所有的容器都可以视作一个“前闭后开”的结构,因此逆序输出，size要减一。数组中存储的是字符类型的数字， 要变成真实整数的值需要 减去一 个字符0
auto C = add(A, B); //auto意为让计算机自己判断变量类型，避免过长类型的重复输入
for (int i = C.size() - 1; i >= 0; i -- ) cout B.size(); //首先比较位数，位数多则大
for (int i = A.size() - 1; i >= 0; i -- ) //其次从高位开始逐位比较，注意高位为最后一个数
if (A[i] != B[i])
return A[i] > B[i];
return true; //如果相等，返回ture
}
vector sub(vector &A, vector &B)
{
vector C;
for (int i = 0, t = 0; i
{
t = A[i] - t;
if (i
C.push_back((t + 10) % 10); //t一定是个位数，A-B大于等于0返回t，小于0则返回t+10， （t+10）%10可包 含两种情况
if (t
else t = 0;
}
while (C.size() > 1 && C.back() == 0) C.pop_back(); //减法有一个问题，比方说123-120，答案是三，a有多少位c就有多少位，所以返回的其实是003，需要把前导零去掉，所以需要一个while循环，只要c的最后一位，首先c的size肯定得大于一。如果它只有一位，是零的话，不能把它减掉，要给它留上一位零，并且最后一位如果等于零的话，就把最后一位去掉。
pop_back()意为删除 vector 的最后一个元素。
return C;
}
int main()
{
string a, b; //这个题并没有考虑很复杂的情况，比方说如果有负数怎么做？如果有负数，不是模板的问题，其实是数输出的问题，需要判断一下a和b这两个字符串，判断第一个字母是不是负号，如果是负号，需要打一个标记。存一下每个数是不是负数，如果两个数相减，有可能是正也有可能是负的，一定可以转化成两数绝对值相减或者绝对值相加的情况，一定可以用两个模板算出来。如果不是正数，需要分情况讨论。
vector 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');
vector C;
if (cmp(A, B)) C = sub(A, B); //判断A是否大于B，大于则A-B，小于则-(B-A)
else C = sub(B, A), cout = 0; i -- ) cout > a >> b;
vector A;
for (int i = a.size() - 1; i >= 0; i -- ) A.push_back(a[i] - '0');
auto C = mul(A, b);
for (int i = C.size() - 1; i >= 0; i -- ) printf("%d", C[i]);
return 0;
}
作者：yxc
链接：https://www.acwing.com/activity/content/code/content/39794/
来源：AcWing
高精度4.除法
人工除法，列数式，比方说1234除上11，首先从第零位开始算，因为计算机不能直接看到第0位不够，所以第零位应该商零，余数是一，把这个余数乘以十。加上下一位数字2，然后下一位是12÷11为一，所以商一余一，把这个余数乘以十，再加上三得13啊，下一位再商一余二，二乘10加4为24，商2余2，最后余数是二。除法也是一个高精度的整数除上一个低精度的整数，假设我们的高精度数是a3a2a1a0除上一个b，每一次就判断一下当前这个余数，这个余数最一开始就只有a3，就直接求a3除b的余数，然后商到这就是最高位c3然后除完之后，余数会变成a3减去一个b×c3，等价于a3除上b的一个余数是多少，余数假设是r1，那么r1乘上十加上下一位a2就会得到a1a2前两位的一个余数，把前两位的一个余数整除b就可以得到c2，同理，再把这个数模上b，得到下一个余数r2，补上下一位r2a1，等于r2乘上十加上a1，因为a的值一直补到余数的后面一位，其实就是r乘10加a1，然后再把这个数除以b求一个商，就是c1，然后再求一下这个数对于b的余数r3，然后最后算一下r3a0这个数除b商是c0，然后最后再算r3a0模b的余数r4
模板题：
给定两个非负整数（不含前导 0） A，B，请你计算 A/B的商和余数。
输入格式
共两行，第一行包含整数 A，第二行包含整数 B。
输出格式
共两行，第一行输出所求的商，第二行输出所求余数。
数据范围
1≤A的长度≤100000,
1≤B≤10000,
B 一定不为 0
输入样例：
72
输出样例：
31
#include
#include
#include
using namespace std; //除法是从最高位开始算的，加法减法乘法都是从最低位开始算，所以如果题目里面只有除法的话啊，正着存数可能会好一些，但是一般情况下，题目里加减乘除这几种运算是混合的，为了能让这几种运算统一起来，在算的时候没有任何的问题。那么除法存储的时候，也是按照前面的存储方式倒着来存。
vector p(vector &A, int b, int &r) //余数r通过引用返回
{
vector 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()); //注意第一位c0存的是最高位，c1存的是最低位。跟前面定义大整数的存法是逆过来的，所以这里需要reverse 1遍，加上算法的头文件。
while (C.size() > 1 && C.back() == 0) C.pop_back(); //去前导0
return C;
}
int main()
{
string a;
vector A;
int B;
cin >> a >> B;
for (int i = a.size() - 1; i >= 0; i -- ) A.push_back(a[i] - '0');
int r;
auto C = p(A, B, r);
for (int i = C.size() - 1; i >= 0; i -- ) cout
