高精度模板

发表于 | | 热度: ℃

存一个高精度模板。

非原创，找不到原文地址了，如果作者看到了可以评论下博客地址，窝再挂上来 QAQ

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
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

const int power = 1, base = 10, N = 10005, SL = 2000;
char a[SL], b[SL];

struct HP
{
    int a[N];
    HP() { memset(a, 0, sizeof(a)); }
    HP(char *s)
    {
        int len = strlen(s);
        memset(a, 0, sizeof(a));
        a[0] = (len + power - 1) / power;
        for(int i = 0, t = 0, w; i < len; w *= 10, i++)
        {
            if(i % power == 0) w = 1, t++;
            a[t] += w * (s[i] - '0');
        }
    }
    void add(int k) { if(k || a[0]) a[++a[0]] = k; }
    void re() { reverse(a + 1, a + a[0] + 1); }
    void print()
    {
        printf("%d", a[a[0]]);
        for(int i = a[0] - 1; i > 0; i--)
            printf("%0*d", power, a[i]);
        printf("\n");
    }
} p, q, ans;

bool operator < (const HP &p, const HP &q)
{
    if(p.a[0] < q.a[0]) return true;
    if(p.a[0] > q.a[0]) return false;
    for(int i = p.a[0]; i > 0; i--)
        if(p.a[i] != q.a[i])
            return p.a[i] < q.a[i];
    return false;
}

HP operator + (const HP &p, const HP &q)
{
    HP c;
    c.a[0] = max(p.a[0], q.a[0]);
    for(int i = 1; i <= c.a[0]; i++)
    {
        c.a[i] += p.a[i] + q.a[i];
        c.a[i + 1] += c.a[i] / base;
        c.a[i] %= base;
    }
    if(c.a[c.a[0] + 1]) c.a[0]++;
    return c;
}

HP operator - (const HP &p, const HP &q)
{
    HP c = p;
    for(int i = 1; i <= c.a[0]; i++)
    {
        c.a[i] -= q.a[i];
        if(c.a[i] < 0) { c.a[i] += base; c.a[i + 1]--; }
    }
    while(c.a[0] > 0 && !c.a[c.a[0]]) c.a[0]--;
    return c;
}

HP operator * (const HP &p, const HP &q)
{
    HP c;
    c.a[0] = p.a[0] + q.a[0] - 1;
    for(int i = 1; i <= p.a[0]; i++)
        for(int j = 1; j <= q.a[0]; j++)
        {
            c.a[i + j - 1] += p.a[i] * q.a[j];
            c.a[i + j] += c.a[i + j - 1] / base;
            c.a[i + j - 1] %= base;
        }
    if(c.a[c.a[0] + 1]) c.a[0]++;
    return c;
}

HP operator / (const HP &p, const HP &q)
{
    HP x, y;
    for(int i = p.a[0]; i > 0; i--)
    {
        y.add(p.a[i]), y.re();
        while(!(y < q)) y = y - q, x.a[i]++;
        y.re();
    }
    x.a[0] = p.a[0];
    while(x.a[0] > 0 && !x.a[x.a[0]]) x.a[0]--;
    return x;
}

int main()
{
    scanf("%s", a), scanf("%s", b);
    reverse(a, a + strlen(a)), reverse(b, b + strlen(b));
    p = HP(a), q = HP(b);
    ans = p + q, ans.print();
    ans = p - q, ans.print();
    ans = p * q, ans.print();
    ans = p / q, ans.print();
    return 0;
}