高精度运算

发表于2022-05-23更新于2022-10-13

高精度运算

利用数组来模拟每一位的加减乘除法，具体分为高精对高精和高精对低精

利用运算符重载来简化使用

输入输出

倒序读入并且第一位存放长度，方便后续的计算和比较

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
char t[10010];
int a[10010];
    BIG_INT(){memset(a, 0, sizeof(a));}
    inline void read()
    {
        scanf("%s", t);
        a[0] = strlen(t);
        for(int i = 0; i < a[0]; i++)
        {
            int j = a[0] - i;
            a[j] = t[i] - '0';
        }
    }

    void print()
    {
        for(int i = a[0]; i >= 1; i--)
            cout << a[i];
        cout << endl;
    }

四则运算

加法

减法

乘法（高精对低精）

1
2
3
4
5
6
7
8
9
10
11
12
13
BIG_INT operator * (const int &b) const
    {
        BIG_INT C;
        int t = 0;
        for(int i = 1; i <= a[0] || t; i++)
        {
            if(i <= a[0]) t += a[i] * b;
            C.a[++C.a[0]] = t % 10;
            t /= 10;
        }
        while(C.a[0] > 1 && C.a[C.a[0]] == 0) C.a[0]--;
        return C;
    }

乘法（高精对高精）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
BIG_INT operator * (const BIG_INT &B) const
    {
        BIG_INT C;
        C.a[0] = a[0] + B.a[0];
        int t = 0;
        for(int i = 1; i <= a[0]; i++)
        {
            t = 0;
            for(int j = 1; j <= B.a[0] || t; j++)
            {
                if(j <= B.a[0]) t += a[i] * B.a[j] + C.a[i + j - 1];
                C.a[i + j - 1] = t % 10;
                t /= 10;
            }
        }
        while(C.a[0] > 1 && C.a[C.a[0]] == 0) C.a[0]--;
        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
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
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
char t[10010];

struct BIG_INT
{
    int a[10010];
    BIG_INT(){memset(a, 0, sizeof(a));}
    inline void read()
    {
        scanf("%s", t);
        a[0] = strlen(t);
        for(int i = 0; i < a[0]; i++)
        {
            int j = a[0] - i;
            a[j] = t[i] - '0';
        }
    }

    inline void print()
    {
        for(int i = a[0]; i >= 1; i--)
            cout << a[i];
        cout << endl;
    }

    bool operator < (const BIG_INT &B) const // A < B
    {
        if(a[0] != B.a[0]) return a[0] < B.a[0];
        for(int i = a[0]; i >= 1; i--)
            if(a[i] != B.a[i]) return a[i] < B.a[i];
        return false;
    }

    void operator = (const BIG_INT &B)
    {
        for(int i = B.a[0]; i >= 0; i--)
            a[i] = B.a[i];
    }

    bool operator == (const BIG_INT &B) const
    {
        if(a[0] != B.a[0]) return false;
        for(int i = a[0]; i >= 1; i--)
            if(a[i] != B.a[i]) return false;
        return true;
    }

    BIG_INT operator - (const BIG_INT &B) const
    {
        BIG_INT C;
        int t = 0;
        for(int i = 1; i <= a[0]; i++)
        {//A - B
            t = a[i] - t;
            if(i <= B.a[0]) t -= B.a[i];
            C.a[++C.a[0]] = (t + 10) % 10;
            if(t < 0) t = 1;
            else t = 0;
        }
        while(C.a[0] > 1 && C.a[C.a[0]] == 0) C.a[0]--;
        return C;
    }

    BIG_INT operator * (const int &b) const
    {
        BIG_INT C;
        int t = 0;
        for(int i = 1; i <= a[0] || t; i++)
        {
            if(i <= a[0]) t += a[i] * b;
            C.a[++C.a[0]] = t % 10;
            t /= 10;
        }
        while(C.a[0] > 1 && C.a[C.a[0]] == 0) C.a[0]--;
        return C;
    }

    BIG_INT operator * (const BIG_INT &B) const
    {
        BIG_INT C;
        C.a[0] = a[0] + B.a[0];
        int t = 0;
        for(int i = 1; i <= a[0]; i++)
        {
            t = 0;
            for(int j = 1; j <= B.a[0] || t; j++)
            {
                if(j <= B.a[0]) t += a[i] * B.a[j] + C.a[i + j - 1];
                C.a[i + j - 1] = t % 10;
                t /= 10;
            }
        }
        while(C.a[0] > 1 && C.a[C.a[0]] == 0) C.a[0]--;
        return C;
    }

    int operator % (const int &b) const
    {
        int t = 0;
        for(int i = a[0]; i >= 1; i--)
        {
            t = t * 10 + a[i];
            t %= b;
        }
        return t;
    }

    BIG_INT operator / (const int &b) const
    {
        BIG_INT C;
        int t = 0;
        for(int i = a[0]; i >= 1; i--)
        {
            t = t * 10 + a[i];
            C.a[0] = max(C.a[0], i);
            C.a[i] = t / b;
            t %= b;
        }
        while(C.a[0] > 1 && C.a[C.a[0]] == 0) C.a[0]--;
        return C;
    }

}A, B, C;

bool check(const BIG_INT &x)
{
    return !(x.a[1] % 2);
}

除法（高精对低精）

1
2
3
4
5
6
7
8
9
10
11
12
void div(int A[], int C[], int b, int &r)
{
	int &len = A[0], &clen = C[0];
	clen = len;
	r = 0;
	for(int i = len, i >= 1; i--){
		r = r * 10 + A[i];
		C[clen + i - len] = r / b;
		r %= b;
	}
	while(clen > 1 && C[clen] == 0) clen--;
}