一、基础算法4：高精度模板题+算法模板（高精度加法，高精度减法，高精度乘法，高精度除法）

﹏ヽ暗。殇╰゛Y 2023-10-08 21:25 10阅读 0赞

#### 文章目录 ####

*  算法模板
 *   *  高精度加法模板
     *  高精度减法模板
     *  高精度乘低精度模板
     *  高精度除以低精度模板
 *  模板题
 *   *  高精度加法
     *   *  原题链接
         *  题目
         *  题解
     *  高精度减法
     *   *  原题链接
         *  题目
         *  题解
     *  高精度乘法
     *   *  原题链接
         *  题目
         *  题解
     *  高精度除法
     *   *  原题链接
         *  题目
         *  题解

## 算法模板 ##

### 高精度加法模板 ###

// C = A + B, A >= 0, B >= 0
    vector<int> add(vector<int> &A, vector<int> &B)
    {
        
        if (A.size() < B.size()) return add(B, A);
    
        vector<int> C;
        int t = 0;
        for (int i = 0; i < A.size(); i ++ )
        {
        
            t += A[i];
            if (i < B.size()) t += B[i];
            C.push_back(t % 10);
            t /= 10;
        }
    
        if (t) C.push_back(t);
        return C;
    }

### 高精度减法模板 ###

// C = A - B, 满足A >= B, A >= 0, B >= 0
    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];
            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;
    }

### 高精度乘低精度模板 ###

// C = A * b, A >= 0, b >= 0
    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()) t += A[i] * b;
            C.push_back(t % 10);
            t /= 10;
        }
    
        while (C.size() > 1 && C.back() == 0) C.pop_back();
    
        return C;
    }

### 高精度除以低精度模板 ###

// A / b = C ... r, A >= 0, b > 0
    vector<int> div(vector<int> &A, int b, int &r)
    {
        
        vector<int> 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) C.pop_back();
        return C;
    }

## 模板题 ##

### 高精度加法 ###

#### 原题链接 ####

[https://www.acwing.com/problem/content/793/][https_www.acwing.com_problem_content_793]

#### 题目 ####

791 . 高精度加法  
给定两个正整数（不含前导 0），计算它们的和。

输入格式  
共两行，每行包含一个整数。

输出格式  
共一行，包含所求的和。

数据范围  
1≤整数长度≤100000  
输入样例：

12
    23

输出样例：

#### 题解 ####

#include <iostream>
    #include <vector>
    using namespace std;
    
    vector<int> add(vector<int> &A,vector<int> &B){
        
    	int t = 0;
    	vector<int> C;
    	for(int i = 0; i<A.size() || i<B.size();i++){
        
    		if(i<A.size()) t+=A[i];
    		if(i<B.size()) t+=B[i];
    		C.push_back(t%10);
    		
    		t /= 10;
    	}
    	
    	if(t) C.push_back(1);
    	
    	return C;
    } 
    
    //vector<int> add(vector<int> &A,vector<int> &B){
        
    //	
    //	if(A.size()<B.size()) return add(B,A);
    //	
    //	int t = 0;
    //	vector<int> C;
    //	//此时A.size()>B.size() 
    //	for(int i = 0; i<A.size();i++){
        
    //		t+=A[i];
    //		if(i<B.size()) t+=B[i];
    //		C.push_back(t%10);
    //		
    //		t /= 10;
    //	}
    //	
    //	if(t) C.push_back(t);
    //	
    //	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'); //注意push_back的是int类型，所以要将char类型-'0' 
    	for(int i = b.size()-1;i>=0;i--) B.push_back(b[i]-'0');
    	
    	auto C = add(A,B);
    	
    	for(int i = C.size()-1;i>=0;i--) cout<<C[i];
    	
    	return 0; 
    }

### 高精度减法 ###

#### 原题链接 ####

[https://www.acwing.com/problem/content/794/][https_www.acwing.com_problem_content_794]

#### 题目 ####

792 . 高精度减法  
给定两个正整数（不含前导 0），计算它们的差，计算结果可能为负数。

输入格式  
共两行，每行包含一个整数。

输出格式  
共一行，包含所求的差。

数据范围  
1≤整数长度≤105  
输入样例：

32
    11

输出样例：

#### 题解 ####

![在这里插入图片描述][7749b254f56c48fbb340421c34b51cb6.png]  
![在这里插入图片描述][908b4292c4a44eb9bddefd7eee0e9fc1.png]  
![在这里插入图片描述][67f5d43ff1d14988bba8616d28ec2398.png]

#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--){
         //从高位开始比，即从vector最后开始 
    		if(A[i]!=B[i]) return A[i]>B[i];
    	}
    	return true; // 到这里证明A=B，因为判断的是A是否>=B所以返回true 
    }
    
    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];  //逻辑应该是t=A[i]-B[i]-t,
    		//但因为A>=B,当A位数大于B时会越界，所以需要加个判断 
    		
    		C.push_back((t+10)%10); //当t>=0时，t需要=t,当t<0时，t需要=t+10,两种情况汇总就是(t+10)%10
    		if(t>=0) t = 0; //借位处理 
    		else t = 1;
    	}
    	
    	while(C.size()>1 && C.back() == 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'); //push_back的要是int类型！ 
    	for(int i=b.size()-1;i>=0;i--) B.push_back(b[i] - '0');
    	
    	vector<int> C;
    	if(cmp(A,B)){
         //A>=B
    		C = sub(A,B);
    		
    		for(int i=C.size()-1;i>=0;i--) cout<<C[i];
    		
    	}
    	else{
        //B>A 相当于转换为 A-B = -(B-A) 
    		C = sub(B,A);
    		
    		cout<<'-';
    		for(int i=C.size()-1;i>=0;i--) cout<<C[i];
    	}
    	return 0;
    }

### 高精度乘法 ###

#### 原题链接 ####

[https://www.acwing.com/problem/content/795/][https_www.acwing.com_problem_content_795]

#### 题目 ####

793 . 高精度乘法  
给定两个非负整数（不含前导 0） A 和 B，请你计算 A×B 的值。

输入格式  
共两行，第一行包含整数 A，第二行包含整数 B。

输出格式  
共一行，包含 A×B 的值。

数据范围  
1≤A的长度≤100000,  
0≤B≤10000  
输入样例：

2
    3

输出样例：

#### 题解 ####

![在这里插入图片描述][345bc1ea59b6479e932d3b40ec6006d4.png]

#include <iostream>
    #include <vector>
    using namespace std;
    
    vector<int> mul(vector<int> &A, int b){
        
    	vector<int> C;
    	
    	for(int i=0,t=0; i<A.size() || t;i++){
         // ||t是处理运算完后t！=0的情况 
    		if(i<A.size()) t = A[i] * b + t; 
    		C.push_back(t%10);
    		t/=10;
    		
    	}	
    	while(C.size()>1 && C.back() == 0) C.pop_back();
    	
    	return C; 
    	
    }
    
    int main()
    {
        
    	int b;
    	string a;
    	cin>>a>>b;
    	vector<int> A;
    	
    	for(int i = a.size()-1;i>=0;i--) A.push_back(a[i] - '0');
    	
    	vector<int> C;
    	
    	C = mul(A,b);
    	
    	for(int i=C.size()-1;i>=0;i--) cout<<C[i];
    	
    	return 0;
    }

### 高精度除法 ###

#### 原题链接 ####

[https://www.acwing.com/problem/content/796/][https_www.acwing.com_problem_content_796]

#### 题目 ####

794 . 高精度除法  
给定两个非负整数（不含前导 0） A，B，请你计算 A/B 的商和余数。

输入格式  
共两行，第一行包含整数 A，第二行包含整数 B。

输出格式  
共两行，第一行输出所求的商，第二行输出所求余数。

数据范围  
1≤A的长度≤100000,  
1≤B≤10000,  
B 一定不为 0  
输入样例：

7
    2

输出样例：

3
    1

#### 题解 ####

![在这里插入图片描述][76510138089a4f10b0883918f5a2943a.jpeg]

#include <iostream>
    #include <vector>
    #include <algorithm>
    using namespace std;
    
    vector<int> div(vector<int> &A,int b,int &r){
        
    	r = 0;
    	vector<int> C;
    	for(int i = A.size() - 1;i>=0;i--){
        
    		r = r * 10 + A[i];
    		C.push_back(r/b);
    		r %= b;
    		
    	}
    //	以上运算完后C中为正序的结果存储，但输出和处理前导0时为逆向处理，所以做一个reverse翻转数组
    	reverse(C.begin(),C.end()); 
    	while(C.size()>1 && C.back() == 0) C.pop_back();
    	
    	return C;
    } 
    int main(){
        
    	int b;
    	string a;
    	cin>>a>>b;
    	vector<int> A;
    	
    	int r;//余数 
    	
    	for(int i = a.size()-1;i>=0;i--) A.push_back(a[i] - '0');
    	
    	vector<int> C;
    	
    	C = div(A,b,r);
    	
    	for(int i=C.size()-1;i>=0;i--) cout<<C[i];
    	cout<<endl<<r;
    	return 0;
    	
    }

[https_www.acwing.com_problem_content_793]: https://www.acwing.com/problem/content/793/
[https_www.acwing.com_problem_content_794]: https://www.acwing.com/problem/content/794/
[7749b254f56c48fbb340421c34b51cb6.png]: https://img-blog.csdnimg.cn/7749b254f56c48fbb340421c34b51cb6.png
[908b4292c4a44eb9bddefd7eee0e9fc1.png]: https://img-blog.csdnimg.cn/908b4292c4a44eb9bddefd7eee0e9fc1.png
[67f5d43ff1d14988bba8616d28ec2398.png]: https://img-blog.csdnimg.cn/67f5d43ff1d14988bba8616d28ec2398.png
[https_www.acwing.com_problem_content_795]: https://www.acwing.com/problem/content/795/
[345bc1ea59b6479e932d3b40ec6006d4.png]: https://img-blog.csdnimg.cn/345bc1ea59b6479e932d3b40ec6006d4.png
[https_www.acwing.com_problem_content_796]: https://www.acwing.com/problem/content/796/
[76510138089a4f10b0883918f5a2943a.jpeg]: https://img-blog.csdnimg.cn/76510138089a4f10b0883918f5a2943a.jpeg