高精度：是指超出long long int的范围的数据，一般用数组存储。

单精度一般是指long long int范围内的数，即可以用基本数据类型表示的数。

1.高精度加法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
//模板题：洛谷P1601
#include<bits/stdc++.h>
using namespace std;
const int N = 505;
string add(string A,string B)
{
	int la=A.length(),lb=B.length();
	int a[N]={0},b[N]={0};
    //字符串转为数组，并且逆序存储，低位在前，方便计算
	for(int i=0;i<la;i++)a[la-i-1]=A[i]-'0';
	for(int j=0;j<lb;j++)b[lb-j-1]=B[j]-'0';
	int lm=la>lb?la:lb;
    //模拟加法运算
	for(int i=0;i<lm;i++){
		a[i]+=b[i],a[i+1]+=a[i]/10,a[i]%=10;	
	}
	if(a[lm])lm++;//最终加法运算可能发生进位，使得位数加1
	string ans;
    //倒序输出
	for(int i=lm-1;i>=0;i--)ans+=a[i]+'0';
	return ans;
}
int main()
{
	string a,b;
	cin>>a>>b;
	cout<<add(a,b)<<endl;
	return 0;
}

2.高精度减法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
//模板题：洛谷P2142 此题需要注意的是，输入的a,b为非负整数 
#include<bits/stdc++.h>
using namespace std;
const int N = 10100;
//判断是否A>=B 
bool cmp(string A,string B)
{
	if(A.size()>B.size() || A>=B && A.size()==B.size())return true;
	return false;
}
string sub(string A,string B)
{
	string ans;
	int a[N]={0},b[N]={0};
	int la=A.size(),lb=B.size();
	for(int i=0;i<la;i++)a[la-1-i]=A[i]-'0';
	for(int i=0;i<lb;i++)b[lb-1-i]=B[i]-'0';
	int lm=la>lb?la:lb;
	for(int i=0;i<lm;i++){
		a[i]-=b[i];
		if(a[i]<0)a[i]+=10,a[i+1]-=1;
	}
    //找到第一个不为0的数
	while(a[lm]==0 && lm>0)lm--;//当lm=0时，即只有一位数的时候，为0也要输出 
	for(int i=lm;i>=0;i--)
		ans+=a[i]+'0';
	return ans;
}
int main()
{
	string a,b;
	cin>>a>>b;
	int flag=0;
	if(!cmp(a,b))flag = 1,swap(a,b);
	if(flag)cout<<"-";
	cout<<sub(a,b)<<endl;
	return 0;
}

3.高精度乘单精度

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
//模板题：http://codeup.cn/problem.php?id=5507
#include<iostream>
#include<string>
using namespace std;
const int N = 250;
string mul(string A,int b)
{
	string ans;
	int a[N]={0};
	int la=A.size();
	for(int i=0;i<la;i++)a[la-1-i]=A[i]-'0';
	int w=0; //w表示上一位相乘得到的进位 
	for(int i=0;i<la;i++){
		a[i]=a[i]*b+w,w=a[i]/10,a[i]%=10;
	}
	while(w>0)a[la++] = w%10,w /= 10; 
	for(int i=la-1;i>=0;i--)ans+= a[i]+'0';
	return ans;
}
int main()
{
	string a;
	int b;
	cin>>a>>b;
	cout<<mul(a,b)<<endl;
	return 0;
}

4.高精度乘高精度

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include<bits/stdc++.h>
using namespace std;
const int N = 300;
string mul(string A,string B)
{
	string ans;
	int a[N]={0},b[N]={0},c[N]={0};
	int la=A.size(),lb=B.size();
	for(int i=0;i<la;i++)a[la-i-1]=A[i]-'0';
	for(int i=0;i<lb;i++)b[lb-i-1]=B[i]-'0';
	//两个数m,n相乘，不进位时(不考虑进制)得到的位数，为m+n-1位 
	for(int i=0;i<la;i++)
		for(int j=0;j<lb;j++)
		//不考虑下标从0开始时，最高位是i,j时，相乘得到的最高位为i+j-1
		//此处下a,b数组下标从零开始，故实际上 (i,j)-1=位数，相乘得最高位为(i+1)+(j+1)-1=i+j-1 
		//c数组也是下标从0开始，故存储的下标为(i+j+1)-1=i+j
			c[i+j] +=a [i]*b[j];
	for(int i=0;i<la+lb;i++)if(c[i]>9)c[i+1] += c[i]/10, c[i] %=10;
	//两个数m,n相乘，考虑进位时，位数至多为m+n位,最少为m+n-1 
	if(c[la+lb-1])ans += c[la+lb-1]+'0';//判断相乘后最高位有没有进位，有则输出，否则最高位为0，不用输出 
	for(int i=la+lb-2;i>=0;i--)ans+=c[i]+'0';
	return ans;
}
int main()
{
	string a,b;
	cin>>a>>b;
	cout<<mul(a,b)<<endl;
	return 0;
}

高精度乘高精度的朴素算法时间复杂度O(n2)，可通过快速傅里叶优化

5.高精度除单精度

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include<bits/stdc++.h>
using namespace std;
const int N = 300;
string div(string a,int b)
{
	int left=0;	//余数 
	string ans;
	for(int i=0;i<a.size();i++){
		ans += (a[i]-'0'+left*10)/b +'0';
		left = (a[i]-'0'+left*10)%b;
	}
	int i=0;
	while(i<ans.size()-1 && ans[i]=='0') i++;
	return ans.substr(i);
}

int main()
{
	string a;
	int b;
	cin>>a>>b;
	cout<<div(a,b)<<endl;
	return 0;
}

6.高精度模单精度

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include<bits/stdc++.h>
using namespace std;
const int N = 300;
//求模，在求除法的过程实际上已经求了余数 
int mod(string a,int b)
{
	int left=0;	//余数 
	for(int i=0;i<a.size();i++){
		left = (a[i]-'0'+left*10)%b;
	}
	return left;
} 
int main()
{
	string a;
	int b;
	cin>>a>>b;
	cout<<mod(a,b);
	return 0;
}

参考:https://blog.csdn.net/u013615904/article/details/43373601