（算法）高精度运算

为什么要有高精度就是因为当数字长度很长的时候都超过了longlong了那么我们就可以通过开数组，集合等方式运算，其原理就是小学生的竖式运算，没想到一个竖式运算竟然可以这么恶，现在的算法已经折磨了后面的路不好走了……

先来搞一下+，-，*，/的高精度运算（都是高进度之间的运算），其实就是进位，取模，借位

加法的关键代码

for(int i=len1-1;i>=0;i--)
    {
        temp=str1[i]-'0'+str2[i]-'0'+cf;
        cf=temp/10;
        temp%=10;
        str=char(temp+'0')+str;
    }
    if(cf!=0)  str=char(cf+'0')+str;
    return str;

减法（得先判断哪一个更大，要大减小）减法会涉及借位当一个数小于一个数的时候：

　　大数减小数

for (int i = 0; i < ans; i ++){
        if (a[i] < b[i]){
            a[i+1] -= 1; // 向前位借一位
            a[i] += 10;  // 后一位就得加10
        }c[i] = a[i] - b[i];  // 之后就是正常减法了
    }
    while (c[ans-1] == 0 && ans > 1)
        ans -= 1;//去除前面的0

　　小数减大数就搞一个flag，然后用大数减小数，比如flag=1那么我们就知道这是一个负数

乘法：对于第i位和第j位相乘其贡献值在i+j-1位（当然这个i和j是我们生活中的位而不是数组中的索引，如果是索引从0开始就不一样）

for (int i = 0; i < str1.size(); i ++) {
	for (int j = 0; j < str2.size(); j ++) {
		c[i+j] += a[i] * b[j];
		c[i+j+1] += c[i+j] / 10;
		c[i+j] = c[i+j] % 10;
	}
}

除法：分两种高精除低精和高精除高精

高精除低精（逐位试商法）

for(i=len-1;i>=0;i--){ //核心计算 
		reminder=reminder*10+a[i]; //模拟竖式除法中的落位 
		ans[i]=reminder/b;
		reminder%=b;
	}

高精除高精：（减法模拟除法）

for(i=len_a-len_b;i>=0;i--){
		while(judge(a+i,b,len_b)){//当a可以被b减的时候一直进行，直到不能被减,即得到最终的商 
			ans[i]++; //记录a被b减的次数，即为除法的结果 
			for(j=0;j<=len_b-1;j++){//高精度减法的实现方法 
				if(a[i+j]<b[j]){
					a[i+j+1]--;
					a[i+j]+=10;
				}
				a[i+j]-=b[j];
			}
		}
	}

每个高精度运算最后输出去除0的时候一定要看运算后最大位数来判断长度并且要添加len>0因为有时候就是输出0

有了以上原理一些高精度运算就可以有其他的板子，比如集合啊七七八八的

//高精乘
void mul(vector<int>& A, int b)
{
	vector<int> res;
	int t = 0;
	for (int i = 0; i < A.size() || t; i++)
	{
		if (i < A.size()) t += A[i] * b;
		res.push_back(t % 10);
		t /= 10;
	}
	while (res.size() > 1 && !res.back()) res.pop_back();
	A = res;
}