高精度
存储方式：数组（可用vector，自带size函数），由低位向高位存各位数字
运算方式：模拟
高精度加法
例：$123+89$
|
0 |
1 |
2 |
3 |
| A |
3 |
2 |
1 |
0 |
| B |
9 |
8 |
0 |
0 |
| C |
2 |
1 |
2 |
0 |
思路：
- 输入两个字符串，并转化成vector
- 循环至两数的最高位，每次判断两个数是否有第$i$位，若有，$t$加上第$i$位，和的第$i$位$=t %10，t/=10$
- 循环完后判断$t$是否为$0$，若不为零，则进位
代码实现：
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
| #include<bits/stdc++.h>
using namespace std;
string a,b;
vector<int>A,B;
vector<int> add(vector<int> &x,vector<int> &y){
vector<int>s;
int t=0;
for(int i=0;i<x.size()||i<y.size();i++){
if(i<x.size())t+=x[i];
if(i<y.size())t+=y[i];
s.push_back(t%10);
t/=10;
}
if(t)s.push_back(t);
return s;
}
int main(){
cin >> a >> b;
for(int i=a.length()-1;i>=0;i--){
A.push_back(a[i]-'0');
}
for(int i=b.length()-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;
}
|
高精度减法
判断$A,B$的大小
当长度不同时，长度越短，大小越小
当长度相同时，从高位循环到低位，若当前位不同，则当前位小的数小
循环到最高位，首先$t=A[i]-t$(减去借位),然后如果$B$有第$i$位，$t$减去$B[i]$，当前位等于$(t+10)%10$（防止负数）,若$t$为负数，则$t=1$(借位标记)，否则$t=0$
循环结束去掉前导$0$
从最高位开始循环直到$size()==1$（结果为$0$时保留），若当前位是0($C.back()==0$),则删除当前位($C.pop_back()$),若当前位不为零，则跳出循环
代码实现：
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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
| #include<bits/stdc++.h>
using namespace std;
string a,b;
vector<int>A,B;
bool operator<(vector<int>x,vector<int>y){
if(x.size()==y.size()){
for(int i=x.size()-1;i>=0;i--){
if(x[i]!=y[i])return x[i]<y[i];
}
return 0;
}
return x.size()<y.size();
}
vector<int> sub(vector<int> &x,vector<int> &y){
vector<int>s;
int t=0;
for(int i=0;i<x.size();i++){
t=x[i]-t;
if(i<y.size())t-=y[i];
s.push_back((t+10)%10);
if(t<0)t=1;
else t=0;
}
while(s.size()>1&&s.back()==0){
s.pop_back();
}
return s;
}
int main(){
cin >> a >> b;
for(int i=a.length()-1;i>=0;i--){
A.push_back(a[i]-'0');
}
for(int i=b.length()-1;i>=0;i--){
B.push_back(b[i]-'0');
}
vector<int>C;
bool flag=0;
if(A<B){
C=sub(B,A);
cout << '-';
}
else{
C=sub(A,B);
}
for(int i=C.size()-1;i>=0;i--){
cout << C[i];
}
return 0;
}
|
高精度乘法
- 双重循环，$C[i+j]=A[i]*B[j]$,处理进位
- 循环结束去掉前导$0$
代码实现：
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
39
40
41
42
43
44
45
46
47
48
| #include<bits/stdc++.h>
using namespace std;
string a,b;
vector<int>A,B;
vector<int> mul(vector<int> &x,vector<int> &y){
vector<int>s;
for(int i=0;i<y.size();i++){
for(int j=0;j<x.size();j++){
if(j+i<s.size()){
s[j+i]+=x[j]*y[i];
}
else{
s.push_back(x[j]*y[i]);
}
if(s[j+i]>9){
if(j+i+1<s.size()){
s[j+i+1]+=s[j+i]/10;
s[j+i]%=10;
}
else{
s.push_back(s[j+i]/10);
s[j+i]%=10;
}
}
}
}
while(s.size()>1&&s.back()==0){
s.pop_back();
}
return s;
}
int main(){
cin >> a >> b;
for(int i=a.length()-1;i>=0;i--){
A.push_back(a[i]-'0');
}
for(int i=b.length()-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;
}
|
高精度除法
- 输入高精度数$A$和长整型数$b$
- 初始$r=0$，从高位向低位循环，每次$r=r*10+A[i]$,则答案的第$i$位为$r/b$，$r=r%b$
- 结束后答案数组是由高位向低位存储，所以翻转数组（$reserve(C.begin(),C.end())$）
- 去掉前导$0$
- $r$即为余数(传入$r$时用$&r$，可以实时改变$r$的真实值)
代码实现：
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
| #include<bits/stdc++.h>
using namespace std;
string a;
long long b;
vector<int>A;
vector<int> div(vector<int> &x,long long y,long long &r){
vector<int>s;
r=0;
for(int i=A.size()-1;i>=0;i--){
r=r*10+A[i];
s.push_back(r/y);
r%=y;
}
reverse(s.begin(),s.end());
while(s.size()>1&&s.back()==0){
s.pop_back();
}
return s;
}
int main(){
cin >> a >> b;
for(int i=a.length()-1;i>=0;i--){
A.push_back(a[i]-'0');
}
long long r;
auto C=div(A,b,r);
for(int i=C.size()-1;i>=0;i--){
cout << C[i];
}
cout << endl << r;
return 0;
}
|
高精度模板：
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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
| #include<bits/stdc++.h>
using namespace std;
vector<int> change(string s){
vector<int>to;
for(int i=s.length()-1;i>=0;i--){
to.push_back(s[i]-'0');
}
return to;
}
vector<int> add(vector<int> &x,vector<int> &y){
vector<int>s;
int t=0;
for(int i=0;i<x.size()||i<y.size();i++){
if(i<x.size())t+=x[i];
if(i<y.size())t+=y[i];
s.push_back(t%10);
t/=10;
}
if(t)s.push_back(t);
return s;
}
bool operator<(vector<int>x,vector<int>y){
if(x.size()==y.size()){
for(int i=x.size()-1;i>=0;i--){
if(x[i]!=y[i])return x[i]<y[i];
}
return 0;
}
return x.size()<y.size();
}
vector<int> sub(vector<int> &x,vector<int> &y){
vector<int>s;
int t=0;
for(int i=0;i<x.size();i++){
t=x[i]-t;
if(i<y.size())t-=y[i];
s.push_back((t+10)%10);
if(t<0)t=1;
else t=0;
}
while(s.size()>1&&s.back()==0){
s.pop_back();
}
return s;
}
vector<int> mul(vector<int> &x,vector<int> &y){
vector<int>s;
for(int i=0;i<y.size();i++){
for(int j=0;j<x.size();j++){
if(j+i<s.size()){
s[j+i]+=x[j]*y[i];
}
else{
s.push_back(x[j]*y[i]);
}
if(s[j+i]>9){
if(j+i+1<s.size()){
s[j+i+1]+=s[j+i]/10;
s[j+i]%=10;
}
else{
s.push_back(s[j+i]/10);
s[j+i]%=10;
}
}
}
}
while(s.size()>1&&s.back()==0){
s.pop_back();
}
return s;
}
vector<int> div(vector<int> &x,long long y,long long &r){
vector<int>s;
r=0;
for(int i=x.size()-1;i>=0;i--){
r=r*10+x[i];
s.push_back(r/y);
r%=y;
}
reverse(s.begin(),s.end());
while(s.size()>1&&s.back()==0){
s.pop_back();
}
return s;
}
int main(){
return 0;
}
|