盛日辉的博客
0%

BigInt实现

发表于 更新于 分类于

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
struct BigInt {
    vector<int> v;

    BigInt(int x) {
        if (x == 0) v.emplace_back(0);
        while (x) {
            v.emplace_back(x % 10);
            x /= 10;
        }
    }

    void multiply(int a) {  // a < 10
        int carry = 0;
        for (int i = 0; i < v.size() || carry; i++) {
            if (i >= v.size()) v.emplace_back(0);
            int t = v[i] * a + carry;
            v[i] = t % 10;
            carry = t / 10;
        }
        // 去掉前导 0，但保留真是 0
        while (v.size() > 1 && v[v.size() - 1] == 0) v.pop_back();
    }

    friend ostream &operator<<(ostream &out, const BigInt &a) {
        if (a.v.empty()) out << 0;
        for (int i = a.v.size() - 1; i >= 0; i--) out << a.v[i];
        return out;
    }
};

BigInt pow(int a, int n) {
    // 算 a 的 n 次方
    BigInt res(1);
    while (n--) {
        res.multiply(a);
    }
    return res;
}

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
#include <stdio.h>
#include <string.h>

#define MAXN 2000

typedef struct {
    int v[MAXN];
    int size;
} BigInt;
void BigInt_print(const BigInt *bi);
BigInt BigInt_init(int x) {
    BigInt b;
    b.size = 0;
    if (x == 0) {
        b.v[b.size++] = 0;
        return b;
    }
    while (x) {
        b.v[b.size++] = x % 10;
        x /= 10;
    }
    return b;
}

void BigInt_add(BigInt *bi, int a) {
    int carry = a;
    int i;
    for (i = 0; i < bi->size || carry; i++) {
        if (i >= bi->size) {
            bi->v[bi->size++] = 0;
        }
        int t = bi->v[i] + carry;
        bi->v[i] = t % 10;
        carry = t / 10;
    }
    while (bi->size > 1 && bi->v[bi->size - 1] == 0) {
        bi->size--;
    }
}

void BigInt_multiply(BigInt *bi, int a) {
    int carry = 0;
    int i;
    for (i = 0; i < bi->size || carry; i++) {
        if (i >= bi->size) {
            bi->v[bi->size++] = 0;
        }
        int t = bi->v[i] * a + carry;
        bi->v[i] = t % 10;
        carry = t / 10;
    }
    while (bi->size > 1 && bi->v[bi->size - 1] == 0) {
        bi->size--;
    }
}

int BigInt_div(BigInt *bi, int a) {
    int p = 0;
    if (bi->v[bi->size - 1] == 1) {
        if (bi->size == 1) {
            bi->v[bi->size - 1] = 0;
            return 1;
        }
        bi->v[bi->size - 1] = 0;
        bi->size--;
        p = 10;
    }
    int i, r = 0;
    for (i = bi->size - 1; i >= 0; i--) {
        p += bi->v[i];
        r = p % a;
        bi->v[i] = p / a;
        p = r * 10;
    }
    return r;
}

void BigInt_print(const BigInt *bi) {
    if (bi->size == 0) {
        printf("0\n");
        return;
    }
    for (int i = bi->size - 1; i >= 0; i--) {
        printf("%d", bi->v[i]);
    }
    printf("\n");
}

void pow_big(int a, int n, BigInt *result) {
    *result = BigInt_init(1);
    while (n--) {
        BigInt_multiply(result, a);
    }
}

题目