算法笔记 - 压位高精

发表于 | 分类于 ，

哎呀！图片走丢了！

介绍

在做题时，题目有时候会要求我们对一些特别大的数进行运算，这些数通常远超过$long\ long$的范围，这时就需要用到高精度算法。高精度算法的原理比较简单，请读者自行百度，这里主要介绍一下压位高精度算法。

在一般的高精度算法中，我们用一个数组的各个元素表示一个大数的各位上的数，但是，一个$int$类的数组的每一个元素可以存储不大于$2147483647$的数，如果每个元素中只存一位数的话岂不是太浪费了，所以我们将多位数压在一起存。使得空间消耗减少，同时也能提高时间效率。

举个栗子，如果我们要存$1234567890$，一般的存法是让$a[0]=0,a[1]=9…$，而用压位高精的话（以压四位为例），就变成$a[0]=7890,a[1]=3456…$，其它的操作不变，还是模拟竖式来做，只不过是一次操作四位罢了。

需要注意的是，使用压位高精，在输出时，除了数组中的最后一个元素，其它的都需要补零输出。

来看看代码吧。

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
128
129
130
131
132
133
134
135
136
137
138
139
#include<bits/stdc++.h>
using namespace std;
const int M=10000,P=4;
struct bignum
{
	int n[5000],l;
	bignum()
	{
		memset(n,0,sizeof(n));
		l=1;
	}
	void read()
	{
		string s;
		cin>>s;
		int now=0,cc=1,ct=0;
		for(int i=s.length()-1;i>=0;i--)
		{
			n[now]+=(s[i]-'0')*cc;
			cc*=10;
			ct++;
			if(ct==P && i!=0)
			{
				now++;
				cc=1;
				ct=0;
			}
		}
		l=now+1;
	}
	void print()
	{
		printf("%d",n[l-1]);
		for(int i=l-2;i>=0;i--)
			printf("%0*d",P,n[i]);
		printf("\n");
	}
	void add(int x)
	{
		if(x || l)
			n[l++]=x;
	}
	void re()
	{
		reverse(n,n+1);
	}
	bool operator < (const bignum &x) const
	{
		bignum t=*this;
		if(t.l!=x.l)
			return t.l<x.l;
		for(int i=t.l-1;i>=0;i--)
			if(t.n[i]!=x.n[i])
				return t.n[i]<x.n[i];
		return 0;
	}
	bignum operator + (const bignum &x) const
	{
		bignum t=*this;
		if(x.l>t.l)
			t.l=x.l;
		for(int i=0;i<t.l;i++)
		{
			t.n[i]+=x.n[i];
			if(t.n[i]>=M)
			{
				t.n[i+1]+=t.n[i]/M;
				t.n[i]%=M;
			}
		}
		while(t.n[t.l])
		{
			t.n[t.l+1]+=t.n[t.l]/M;
			t.n[t.l++]%=M;
		}
		return t;
	}
	bignum operator - (bignum x) const
	{
		bignum t=*this;
		if(t<x)
		{
			printf("-");
			swap(t,x);
		}
		for(int i=0;i<t.l;i++)
		{
			t.n[i]-=x.n[i];
			if(t.n[i]<0)
			{
				t.n[i]+=M;
				t.n[i+1]--;
			}
		}
		while(!t.n[t.l-1] && t.l>1)
			t.l--;
		return t;
	}
	bignum operator * (const bignum &x) const
	{
		bignum t=*this,tmp;
		tmp.l=t.l+x.l-1;
		for(int i=0;i<t.l;i++)
			for(int j=0;j<x.l;j++)
			{
				tmp.n[i+j]+=t.n[i]*x.n[j];
				if(tmp.n[i+j]>=M)
				{
					tmp.n[i+j+1]+=tmp.n[i+j]/M;
					tmp.n[i+j]%=M;
				}
			}
		while(tmp.n[tmp.l])
		{
			tmp.n[tmp.l+1]+=tmp.n[tmp.l]/M;
			tmp.n[tmp.l++]%=M;
		}
		return tmp;
	}
	bignum operator / (const int &x) const
	{
		bignum t=*this,r;
		int tmp=0;
		r.l=t.l;
		for(int i=t.l-1;i>=0;i--)
		{
			tmp+=t.n[i];
			if(tmp>=x)
			{
				r.n[i]+=tmp/x;
				tmp%=x;
			}
			tmp*=M;
		}
		while(!r.n[r.l-1] && r.l>1)
			r.l--;
		return r;
	}
};
0%