高精度

• 1. 高精度加法（高精+高精）
• 2. 高精度减法（高精-高精）
• 3. 高精度乘法
  • 3.1. 高精×低精
  • 3.2. 高精×高精
• 4. 高精度除法
  • 4.1. 高精÷低精
  • 4.2. 高精÷高精

1. 高精度加法（高精+高精）

• 基于数组

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

// 定义全局变量,初始化每个元素都为0
int a[MAX_SIZE];
int b[MAX_SIZE];
int c[MAX_SIZE+1]; // 最多200+1位

int main() {
	// 高精度加法问题
	// 输入大整数
	string s1,s2;
	cin>>s1>>s2;
	int n1=s1.length();
	int n2=s2.length();
	
	// 逆序存储大整数到数组中
	for(int i=0;i<n1;i++) {
		a[i]=s1[n1-1-i]-'0';
	}
	for(int i=0;i<n2;i++) {
		b[i]=s2[n2-1-i]-'0';
	}
		
	// 模拟竖式加法进行计算
	int n3=max(n1,n2)+1; // 最多再进一位
	for(int i=0;i<n3;i++) {
		c[i]+=a[i]+b[i];
		if(c[i]/10) {
			// c[i+1]+=c[i]/10; // 这里也可以改为c[i+1]+=1 因为最多也就9+9=18,进1位
			c[i+1]+=1;
			c[i]%=10;
		}
	}
	
	// 去除前导0
	while(c[n3]==0 && n3>0) {
		n3--;
	}
	
	// 逆序输出
	for(int i=n3;i>=0;i--) {
		cout<<c[i];
	}
	return 0;
}

• 基于STL

#include<bits/stdc++.h>
#define x first
#define y second
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> PII;

const int N=1e6+10; // 最大长度

// 加引用是为了提高效率,没有引用的话会再copy一遍
// C=A+B
vector<int> add(vector<int> &A,vector<int> &B) {
	vector<int> C;
	int t=0; // 保留上一位的进位
	
	// "||"保证了A和B谁的数位更高或更低都能计算
	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;
	}
	// 如果最高位还要进位的话,就补个1
	if(t) C.push_back(1);
	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');
	
	auto C=add(A,B); 
	
	for(int i=C.size()-1;i>=0;i--) cout<<C[i];
	
	return 0;
}

2. 高精度减法（高精-高精）

重点在于判定是A大还是B大

• 基于数组

#include<bits/stdc++.h>
#define MAXN 200
using namespace std;
int a[MAXN];
int b[MAXN];
int c[MAXN];
int main() {
	
	// 高精度减法两种情况
	// 输入大整数
	string s1,s2;
	cin>>s1>>s2;
	int n1=s1.length();
	int n2=s2.length();
	
	// 判断哪个数字更大
	if(n1<n2 || (n1==n2 && s1<s2)) {
		swap(s1,s2);
		cout<<'-';
		// 如果交换了,n1和n2要更新一下
		n1=s1.length();
		n2=s2.length();
	}
	
	// 逆序存储,最后都用a-b
	for(int i=0;i<n1;i++) {
		a[i]=s1[n1-i-1]-'0';
	}
	for(int i=0;i<n2;i++) {
		b[i]=s2[n2-i-1]-'0';
	}

	// 竖式相减
	int n3=max(n1,n2);
	for(int i=0;i<n3;i++) {
		c[i]+=a[i]-b[i];
		if(c[i]<0) {
			c[i+1]--;
			c[i]+=10;
		}
	}
	
	// 去除前导0
	while(c[n3]==0 && n3>0) {
		n3--;
	}
	
	// 逆序输出
	for(int i=n3;i>=0;i--) {
		cout<<c[i];
	}
	return 0;
}	

• 基于STL

#include<bits/stdc++.h>
#define x first
#define y second
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> PII;

// 判断是否有A>=B
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的子集
}

// C=A-B(A>=B)
vector<int> sub(vector<int> &A,vector<int> &B) {
	vector<int> C;
	int t=0; // 保留进位
	for(int i=0;i<A.size();i++) {
		t=A[i]-t;
		// 判断B[i]是否存在,因为B的位数可能比A更小
		if(i<B.size()) t-=B[i];
		C.push_back((t+10)%10); // 如果t>=0,则(t+10)%10=t;如果t<0,则(t+10)%10变为正数
		if(t<0) t=1; // 借位,再算下一位的时候要多减去一个1
		else t=0; // 不借位
	}
	
	// 去前导0(vector做高精加的话就不会出现前导0,相减的话可能出现003这种数字)
	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');
	for(int i=b.size()-1;i>=0;i--) B.push_back(b[i]-'0');
	
	if(cmp(A,B)) {
		auto C=sub(A,B);
		for(int i=C.size()-1;i>=0;i--) cout<<C[i];
	} else {
		auto C=sub(B,A);
		cout<<"-";
		for(int i=C.size()-1;i>=0;i--) cout<<C[i];
	}
	
	return 0;
}

3. 高精度乘法

3.1. 高精×低精

• 基于数组

#include<bits/stdc++.h>
#define x first
#define y second
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> PII;

const int N=1e5+10;
string str;
int len1,len2;
int a[N],b,c[N];

void mul(int a[],int b) {
	int t=0;
	for(int i=1;i<=len1||t;i++) {
		if(i<=len1) t+=a[i]*b;
		c[++len2]=t%10;
		t/=10;
	}
	// 去前导0
	while(c[len2]==0 && len2>1) len2--;
}

int main() {
	cin>>str>>b;
	len1=str.length();
	for(int i=1;i<=len1;i++) a[i]=str[len1-i]-'0'; // 将数a倒序
	mul(a,b);
	for(int i=len2;i>=1;i--) cout<<c[i];
	return 0;
}

• 基于STL

#include<bits/stdc++.h>
#define x first
#define y second
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> PII;

vector<int> mul(vector<int> &A,int b) {
	vector<int> C;
	int t=0;
	// 如果有"||t"就不用单独处理剩余的t了,只要t不是0就会一直处理t的进位
	for(int i=0;i<A.size() || t;i++) {
		if(i<A.size()) t+=A[i]*b;
		C.push_back(t%10); // 只取个位
		t/=10;
	}
	// 处理最后剩余的t
//	while(t) {
//		C.push_back(t%10);
//		t/=10;
//	}
	// 为了避免1234*0=0000的这种情况,还是需要去除前导0
	while(C.size()>1 && C.back()==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');
	auto C=mul(A,b);
	for(int i=C.size()-1;i>=0;i--) cout<<C[i];
	return 0;
}

3.2. 高精×高精

• 基于数组

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

char s1[MAXN];
char s2[MAXN];
int a[MAXN];
int b[MAXN];
int c[MAXN+MAXN]; // 100(3)*100(3)=10000(6)
	
int main() {
	// 高精度乘法
	// 输入大整数
	// 这里如果用gets,在信奥一本通上无法通过
	// cin.getline(s1,MAXN);
	// cin.getline(s2,MAXN);
	cin>>s1;
	cin>>s2;
	int n1=strlen(s1);
	int n2=strlen(s2);
	
	// 逆序存储
	for(int i=0;i<n1;i++) {
		a[i]=s1[n1-i-1]-'0';
	}
	for(int i=0;i<n2;i++) {
		b[i]=s2[n2-i-1]-'0';
	}
	
	// 竖式乘法
	int n3=n1+n2;
	for(int i=0;i<n1;i++) {
		for(int j=0;j<n2;j++) {
			c[i+j]+=a[i]*b[j];
			if(c[i+j]>=10) // 说明要进位
			{
				c[i+j+1]+=c[i+j]/10;
				c[i+j]%=10;
			}
		}
	}
	
//	// 处理进位问题
//	for(int i=0;i<n3;i++) {
//		c[i+1]+=c[i]/10; 
//		c[i]%=10;
//	}
	
	// 处理前导0
	while(c[n3]==0 && n3>0) {
		n3--;
	}
	
	// 逆序输出
	for(int i=n3;i>=0;i--) {
		cout<<c[i];
	}
	
	return 0;
}

• 基于STL

#include<bits/stdc++.h>
#define x first
#define y second
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> PII;

vector<int> mul(vector<int> &A,vector<int> &B) {
	vector<int> C(A.size()+B.size(),0); // C最大数位为size_A+size_B,如100(3)×100(3)=10000(5)
	// 对C预开大小,是为了用类似于数组的方式来操控C
	// 因为A[i]要乘以每一位B[j]
	for(int i=0;i<A.size();i++) {
		for(int j=0;j<B.size();j++) {
			C[i+j]+=A[i]*B[j];
			// 说明需要进位
			if(C[i+j]>=10) {
				C[i+j+1]+=C[i+j]/10;
				C[i+j]%=10;
			}
		}
	}	
	
	// 去除前导0,因为开了大小为A.size()+B.size()的全为0的数组,有可能用不完这些空间
	while(C.size()>1 && C.back()==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');
	auto C=mul(A,B);
	for(int i=C.size()-1;i>=0;i--) cout<<C[i];
	return 0;
}

4. 高精度除法

4.1. 高精÷低精

• 基于数组

#include<bits/stdc++.h>
const int maxn=1e2+2;
using namespace std;

int N[maxn]; // 存放大整数
int ans[maxn]; // 存放商数
int b=13; // 余数
// 高精度除以低精度
int main() {
	string s;
	cin>>s;
	int n1=s.length();
	int x=0; 
	for(int i=0;i<n1;i++) {
		ans[i]=(x*10+(s[i]-'0'))/b; // 记录余数
		x=(x*10+(s[i]-'0'))%b; // 余数继续参与计算
	}
	// 去除ans的前导0
	int n2=0;
	while(ans[n2]==0 && n2<n1) {
		n2++;
	}
	// 打印出商数
	for(int i=n2;i<n1;i++) {
		cout<<ans[i];
	}
	cout<<endl;
	// 打印余数
	cout<<x;
	return 0;
}

• 基于STL

#include<bits/stdc++.h>
#define x first
#define y second
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> PII;

// 传地址方便直接对余数r进行修改
vector<int> div(vector<int> &A,int B,int &r) {
	vector<int> C;
	for(int i=0;i<A.size();i++) {
		r=r*10+A[i];
		C.push_back(r/B); // 商
		r=r%B; // 余数
	}
	// 由于除法运算中高位到低位运算,因此C的前导0都在vector的前面而不是尾部
	// 所以反转C,这样0就位于数组尾部,从而用pop删除前导0
	reverse(C.begin(),C.end());
	while(C.size()>1 && C.back()==0) C.pop_back();
	return C;
}

int main() {
	string str;
	int B,r=0; // 代表余数
	cin>>str>>B;
	vector<int> A;
	for(int i=0;i<str.size();i++) A.push_back(str[i]-'0');
	auto C=div(A,B,r);
	for(int i=C.size()-1;i>=0;i--) cout<<C[i]; // 再逆序一遍变成正序
	cout<<endl<<r<<endl; // 余数
	return 0;
}

4.2. 高精÷高精

用数组模拟是非常麻烦的，这里只介绍基于STL库中的vector实现方法

• 基于STL

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

// 比较A和B谁更大
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;
}

// r:存储每次迭代后的余数
// C:存储每次返回后组成的商数
vector<int> div(vector<int> &A, vector<int> &B, vector<int> &r){
	vector<int> C; 
	int j = B.size();
	// 比如12345÷67,j=2,那么初始余数就为45
	r.assign(A.end()-j,A.end()); // 初始化余数r为A的最后j位
	// 当j小于等于A的长度时循环
	while(j<=A.size()) {
		int k=0;
		// 当余数r大于等于B时循环
		while(cmp(r,B)){
			// 利用高精减计算r-B的结果
			vector<int> s = sub(r,B);
			r.clear();
			// 将结果赋值给r
			r.assign(s.begin(),s.end());
			k++; // 商+1
		} 
		C.push_back(k); // 存储商
		// 如果j小于A的长度,则将A中的下一位加入到余数r的最前面
		if(j<A.size()) r.insert(r.begin(),A[A.size()-j-1]);
		// 去掉余数0,因为随时要进行下一轮的计算
		if(r.size()>1&&r.back()==0) r.pop_back();
		j++;
	}
	// 反转结果,因为要利用高精减必须从低位开始
	reverse(C.begin(),C.end());
	// 去掉前导0
	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');
	
	auto C = div(A,B,r);
	for(int i=C.size()-1;i>=0;i--) printf("%d",C[i]);
	printf("\n");
	for(int i=r.size()-1;i>=0;i--) printf("%d",r[i]);
	return 0;
}

打赏