高精度算法

发表于 更新于 分类于 阅读次数：
本文字数： 5.3k 阅读时长 ≈ 5 分钟

高精度加法

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