高精度算法

高精度加法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
// A和B存储要倒着存储 for(n-1:>=0;)

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

if (t) C.push_back(t);
return C;
}

P1601高精度加法

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
#include <iostream>
#include <cstring>
#include <vector>

using namespace std;

vector<int> A,B;

vector<int> add(vector<int> A,vector<int> B)
{
vector<int> C;
int t=0;
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(t);
return C;

}

int main()
{
string a,b;
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--)
{
printf("%d",c[i]);
}

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

//比较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;
}

// C = A - B, 满足A >= B, A >= 0, B >= 0

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;
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;
}

int main(){
//---读入数组
//A和B都是正数

if(cmp(A,B)){
auto c = sub(A,B);
//---输出
}
else
{
auto c=sub(B,A);
printf("-");//结果是负数
//---输出
}
}

P2142高精度减法

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
#include <iostream>
#include <cstring>
#include <vector>

using namespace std;


vector<int> A,B;
string a,b;

bool cmp(vector<int> A,vector<int> B)
{
if(A.size()!=B.size()) return A.size()>B.size();
for(int i=0;i<A.size();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();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;
}

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

if(cmp(A,B)){

auto c=sub(A,B);
for(int i=c.size()-1;i>=0;i--)
{
printf("%d",c[i]);
}

}else{
auto c=sub(B,A);

printf("-");
for(int i=c.size()-1;i>=0;i--)
{
printf("%d",c[i]);
}
}

return 0;
}


高精度乘法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
// 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(); i ++ )
{
if (i < A.size()) t += A[i] * b;
C.push_back(t % 10);
t /= 10;
}

if (t) C.push_back(t);
return C;
}


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

#include <iostream>
#include <cstring>
#include <vector>

using namespace std;

vector<int> A;
int b;


vector<int> mul(vector<int> A,int b)
{

vector<int> C;
int t=0;
for(int i=0;i<A.size();i++)
{

if(i<A.size()) t+=A[i]*b;
C.push_back(t%10);
t/=10;

}

if(t) C.push_back(t);

while (C.size() > 1 && C.back() == 0) C.pop_back();
return C;

}


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

for(int i=a.length()-1;i>=0;i--)
{
A.push_back(a[i]-'0');
}

auto c=mul(A,b);
for(int i=c.size()-1;i>=0;i--)
{
printf("%d",c[i]);
}


return 0;
}


高精度除法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
//r是余数
// A / b = C ... r, A >= 0, b > 0
// 需要输出余数,把r设为全局变量,或者用引用
// 这样写也行,需要就输出,不需要就不输出
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;
}



P1480 A/B

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
1e9会爆int,加上这一句 #define int long long
int main函数改为signed main()


#include <iostream>
#include <cstring>
#include <vector>
#include <algorithm>
#define int long long
using namespace std;

vector<int> A;
int b;
string a;

vector<int> div(vector<int> A,int b)
{
vector<int> C;

//如果需要输出r,把他改为全局变量
int 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;
}



signed main()
{

cin>>a>>b;

for(int i=a.length()-1;i>=0;i--)
{
A.push_back(a[i]-'0');
}

auto c=div(A,b);


for(int i=c.size()-1;i>=0;i--)
{
printf("%d",c[i]);
}

return 0;
}