大数四则运算模板

参考：

https://www.xuebuyuan.com/1860973.html

大数加法

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
#include <iostream>
#include <string>
using namespace std;

const int MAXN = 1e6;
int ia[MAXN];
int ib[MAXN];
int ans[MAXN];

int main()
{
    string sa, sb;
    cin >> sa >> sb;
    int la = sa.size();
    int lb = sb.size();
    int ml = la > lb ? la : lb;
    for(int i = 0; i < la; i++)
        ia[i] = sa[la - i - 1] - '0';
    for(int i = 0; i < lb; i++)
        ib[i] = sb[lb - i - 1] - '0';
    int next = 0;
    for(int i = 0; i < ml; i++)
    {
        ans[i] = (ia[i] + ib[i] + next) % 10;
        next = (ia[i] + ib[i] + next) / 10;
    }
    if(next > 0)
        cout << next;
    for(int i = ml - 1; i >= 0; i--)
        cout << ans[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
50
51
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;

const int MAXN = 1E6;
int ia[MAXN];
int ib[MAXN];
int ans[MAXN];

int main()
{
    string sa, sb;
    cin >> sa >> sb;
    if(sa == sb)
    {
        cout << "0";
        return 0;
    }
    int flag = 0;
    int la = sa.size();
    int lb = sb.size();
    //默认取sa大于sb，如果sb大于sa，那么需要交换，并且在输出结果前面加上-
    if(lb > la || (la == lb && sb > sa))
    {
        swap(sa, sb);
        swap(la, lb);
        flag = 1;
    }
    for(int i = 0; i < la; i++)
        ia[i] = sa[la - i - 1] - '0';
    for(int i = 0; i < lb; i++)
        ib[i] = sb[lb - i - 1] - '0';
    for(int i = 0; i < la; i++)
    {
        ia[i] -= ib[i];
        if(ia[i] < 0)
        {
            ia[i] += 10;
            ia[i + 1]--;
        }
    }
    int j = la - 1;;
    while(ia[j] == 0)
        j--;
    if(flag)
        cout << "-";
    for(;j >= 0; j--)
        printf("%d", ia[j]);
    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
50
51
52
53
54
55
56
57
58
#include <iostream>
#include <algorithm>
#include <string>
#include <cstring>
using namespace std;

const int MAXN = 1E3;
int ia[MAXN];
int ib[MAXN];
int ic[MAXN];

int main()
{
    string sa, sb;
    cin >> sa >> sb;
    int la = sa.size();
    int lb = sb.size();
    memset(ia, 0, sizeof(ia));
    memset(ib, 0, sizeof(ib));
    //默认取sa大于sb，如果sb大于sa，那么需要交换，因为涉及到后面的2×la，方便处理
    if(lb > la || (lb == la && lb > la))
    {
        swap(sa, sb);
        swap(la, lb);
    }
    for(int i = 0; i < la; i++)
        ia[i] = sa[la - i - 1] - '0';
    for(int i = 0; i < lb; i++)
        ib[i] = sb[lb - i - 1] - '0';
    for(int i = 0; i < lb; i++)
    {
        for(int j = 0; j < la; j++)
        {
            ic[i + j] = ic[i + j] + ia[j] * ib[i];
        }
    }

    for(int i = 0; i < 2 * la; i++)
    {
        if(ic[i] > 10)
        {
            ic[i + 1] = ic[i + 1] + ic[i] / 10;
            ic[i] = ic[i] % 10;
        }
    }

    int j = 2 * la;
    while(ic[j] == 0)
        j--;
    if(j < 0)
    {
        cout << "0";
        return 0;
    }
    for(;j >= 0; j--)
        cout << ic[j];
    return 0;
}

大数除法

参考：
http://www.cnblogs.com/wuqianling/p/5387099.html

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

const int MAXN = 1e2;

/*
函数sub功能： 
用长度为len1的大整数num1减去长度为len2的大整数num2 
结果存在num1中，返回值代表结果的长度 
不够减：返回-1 ， 正好够：返回0
*/    
int sub(int *num1, int len1, int *num2, int len2)
{
    if(len1 < len2)
        return -1;

    if(len1 == len2) //两数字位数相同时，对比哪个数大
    {
        for(int i = len1 - 1; i >= 0; i--)
        {
            if(num1[i] > num2[i]) //num1大，满足条件
                break;
            else if(num1[i] < num2[i]) //当n2大于n1时，此时不够减，返回－1
                return -1;
        }
    }

    for(int i = 0; i <= len1 - 1; i++) //减法操作
    {
        num1[i] -= num2[i];
        if(num1[i] < 0) //需要借位
        {
            num1[i] += 10;
            num1[i + 1]--;
        }
    }

    for(int i = len1 - 1;i >= 0; i--) //去除前导0，查找结果最高位。
    {
        if(num1[i])
            return i + 1;
    }
    return 0; //两数相等时返回0
}

/* 大数除法---结果不包括小数点 
num1 / num2  
ans:结果数组,商，存放计算的结果，
即：num1/num2=ans
返回数组ans的有效长度，即商的位数 
*/ 
int division(char* num1, char* num2, char* ans)
{
    int len1 = strlen(num1);
    int len2 = strlen(num2);
    int num_a[MAXN] = {0};
    int num_b[MAXN] = {0};
    int num_c[MAXN] = {0};

    for(int i = 0; i < len1; i++) //将字符数字每个数字处理为int，然后倒序存在另外一个数组
        num_a[i] = num1[len1 - i - 1];
    for(int i = 0; i < len2; i++)
        num_b[i] = num2[len2 - i - 1];

    if(len1 < len2) //如果被除数小于除数，直接返回-1，表示结果为0
        return -1;
    
    int dvalue = len1 - len2; //两大数相差位数
    
    //进行扩展，不是一个个减，而是以其10的倍数减，刚开始扩展到与被除数相等的位数，即相当于乘以10的x次方
    for(int i = len1 - 1; i >= 0; i--) 
    {
        if(i >= dvalue)
            num_b[i] = num_b[i - dvalue];
        else
            num_b[i] = 0;
    }
    
    len2 = len1;
    int n;
    //进行减法
    for(int i = 0; i <= dvalue; i++)
    {
    	//num_b + i代表不断尝试10的x次方,因为其后面为0,故相当于乘以10的x次方
        while((n = sub(num_a, len1, num_b + i, len2 - i)) >= 0) //不断尝试将除数扩大来减
        {
            len1 = n;
            num_c[dvalue - i]++; 
            //对应的结果位数++，刚开始加的位数很大，比如百位，然后除数逐渐减少，对应的就会加在十位个位
        }
    }
    
    int j;
	//跳过高位0，获取商的位数
    for(j = MAXN - 1; j >= 0; j--)
    {
        if(num_c[j] != 0)
            break;
    }
    int len = -1; //商的位数
    if(j >= 0)
        len = j + 1;
    //因为得到的结果是倒序的，故倒序将结果复制到ans数组
    for(int i = 0; j >= 0; i++, j--)
        ans[i] = num_c[j];
    ans[j] = '\0';
    return len;
}

int main()
{
    char num1[MAXN] = "1234567899876543210";
    char num2[MAXN] = "20160415123025";
    char ans[MAXN];

    int len = division(num1, num2, ans);
    if(len >= 0)
    {
        for(int i = 0; i < len; i++)
            cout << ans[i];
    }
    else
        cout << "0";
    return 0;
}