高精度算法

(1)高精度加法

首先，对字符串进行处理

string a,b;
cin>>a>>b;
vector<int>A(a.size());
vector<int>B(b.size());
for(int i=0;i<a.size();i++)A.push_back(a[i]-'0');
for(int i =0;i<.size();i++)B.push_back(b[i]-'0');

转换为vector数组并倒转数字{
        //为什么？：1.在处理加法时，如果顺序存储，最高位就是A[0],如果最高位要进位，需要在a[0]前加一个数，显然会很麻烦(要移动数组每一位)，换一种想法，只需要将数字倒过来相加，最高位在数组最末位，进位时只需要在数组最后添加一个数，显然大大提升了效率

接下来处理高精度加法函数

vector<int> add(vector<int> &A,vector<int> &B){
vector<int>C;
int carry=0;//处理进位
for(int i=0;i<A.size()||i<B.size();i++){
if(i<A.size())carry+=A[i];
if(i<B.size())carry+=B[i];
C.push_back(carry%10);
carry/=10;
}
if(carry!=0)C.push_back(carry);
return C;
}

   将ab的每一位拿出来相加，存储carry的个位数存入C数组即可，假设从开始相加，carry为0,此时a与b的个位数相加，没进位，直接存入carry/=10;carry归零，如果进位，将carry个位数取出存入后，carry/=10;将进位存储在下一次加法的初始carry中，即可完成进位

最后，输出总结：

#include <bits/stdc++.h>
using namespace std;

// 高精度加法：C = A + B
vector<int> add(vector<int> &A, vector<int> &B) {
vector<int> C;
int carry = 0; // 进位

for (int i = 0; i < A.size() || i < B.size(); i++) {
if (i < A.size()) carry += A[i];
if (i < B.size()) carry += B[i];
C.push_back(carry % 10);
carry /= 10;
}

if (carry) C.push_back(carry); // 最后的进位
return C;
}

int main() {
string a, b;
cin >> a >> b;

// 转换为vector，低位在前
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 = add(A, B);

// 输出结果（从高位到低位）
for (int i = C.size() – 1; i >= 0; i–) cout << C[i];
cout << "\\n";

return 0;
}

(2)高精度减法

第一步与加法相同，存储数字进入数组即可

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');

接下来，写一个函数判断a,b大小再进行减法

bool compare(string a, string b) {
if (a.length() != b.length())
return a.length() > b.length();
return a > b;
}

接下来我们写减法函数，对于减法函数，在这里我们只考虑a>=b的情况，因为我们的vector数组不能存储负数，对于a<b的情况，我们在主函数中分情况讨论，a<b时，就交换计算b-a的情况，然后再添加负号

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()) t -= B[i]; // 再减去B[i]
C.push_back((t + 10) % 10); // 结果
t = t < 0 ? 1 : 0; // 如果t<0，需要借位
}
// 去掉前导零
while (C.size() > 1 && C.back() == 0) C.pop_back();
return C;
}

为什么要(t+10)%10?:这是因为在减法的时候有两种情况，这一位够减了，对于+10再%10没有影响，而这一位不够减时，加10再%10就是向前借一位再减

前导零？：在减法时，可能会出现减法后由原本的位数减为少一位的情况，这时候就会产生前导零

最后，减法模板

#include <iostream>
#include <vector>
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;
}
// 高精度减法 A – B（要求 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()) t -= B[i]; // 再减去B[i]
C.push_back((t + 10) % 10); // 结果
t = t < 0 ? 1 : 0; // 如果t<0，需要借位
}

// 去掉前导零
while (C.size() > 1 && C.back() == 0) C.pop_back();
return C;
}

int main() {
string a, b;
vector<int> A, B;

cin >> a >> b;

// 读取A（倒序存储）
for (int i = a.length() – 1; i >= 0; i–)
A.push_back(a[i] – '0');

// 读取B（倒序存储）
for (int i = b.length() – 1; i >= 0; i–)
B.push_back(b[i] – '0');

// 判断大小并计算
if (cmp(A, B)) {
vector<int> C = sub(A, B);
for (int i = C.size() – 1; i >= 0; i–)
cout << C[i];
} else {
cout << "-";
vector<int> C = sub(B, A);
for (int i = C.size() – 1; i >= 0; i–)
cout << C[i];
}

return 0;
}

(3)高精度乘法

高精度乘法一般分两种，一种高精度X低精度，一种高精度X高精度

1.高精度×低精度

这种比较简单，列出处理进位即可

与前面几种类似；

#include<iostream>
#include<vector>
using namespace std;

vector<int> multiply(const vector<int>&A,long long b) {
vector<int> C;
long long t=0;
for(int i=0;i<A.size()||t;i++) {
if (i < A.size()) t += A[i] * b;
C.push_back(t%10);
t/=10;
}
while(C.size()>1&&C.back()==0)C.pop_back();
return C;
}

int main(){
string a;
long long b;
cin>>a>>b;
vector<int>A;
for(int i=a.size()-1;i>=0;i–)A.push_back(a[i]-'0');
vector<int> ans=multiply(A,b);
for(int i=ans.size()-1;i>=0;i–)cout<<ans[i]<<" ";

return 0;
}

2.高精度×高精度

这里有一个比较重要的地方:竖式乘法中A的第i位置乘以B的第j位得到的数字应该在第i+j位置上，其余基本与前几项相同，不过要单独处理进位

#include<iostream>
#include<vector>
using namespace std;

vector<int> multiply(const vector<int>&A,const vector<int>&B) {
vector<int>C(A.size()+B.size(),0);
for(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<A.size()+B.size();i++) {
t+=C[i];
C[i]=t%10;
t/=10;
}
while (C.size()>1&&C.back()==0)C.pop_back();
return C;
}

int main() {
string a,b;
cin>>a>>b;
vector<int>A;
vector<int>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>ans=multiply(A,B);
for (int i=ans.size()-1;i>=0;i–)cout<<ans[i]<<" ";
return 0;
}