高精度压位

高精度压位

九月 05, 2021

压位的原因

正常的高精度计算中，每一位只存了一位数字，可是当面对比较大的计算的时候呢，如果说每一位都只存一位数字，那么计算的时间就会比较地长。这个时候可以通过每一位高精度中存储多位数字的方法来降低运算的时间

例题引入

简单的来说就是 一个高精度的开根号，只要求开到整数向下取整就可以了。数据范围是$10^{1000}$;
首先就是开高精度根号的方法，很容易想到的方法就是二分或者是手动开根号。我这里使用的是二分的方法。
这一道题最开始我是直接高精度来的,然后TLE了，接着我压了四位，还是TLE了，然后直接$10000000$一位了，终于A了。
那么接下来我来一点点解析代码(实际上我只解析读入而已了)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
inline void input(){ // 读入  
		char S[maxn];
		scanf("%s",S);
		memset(val,0,sizeof(val));
		int lenS=strlen(S); 
		int j=0;
		for(int i=lenS-1;i>=0;i-=7){//因为是10^8的进制，所以给7位
			int t=max(i-6,0),res=0;//i-6~i一共七位，
			while(t<=i){
				res=res*10+S[t]-'0';
				t++;
			}
			val[++j]=res;
		}
		val[0]=j;
	}

我的解析全写注释了，实际上总共我也只有两句解析，因为我在这两个地方没怎么注意，所以最开始我……
至于这一个高精度的其他部分，那么就直接把10改成对应的大小就可以了，我这里是$10^8$

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
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
#include<bits/stdc++.h>
#define Int64 long long
#define carries 10000000
#define maxn 1003
using namespace std;
struct largenum{  
	Int64 val[maxn];
	Int64 operator [](const int &ref)const{
		return val[ref];
	}
	
	inline void input(){ // 读入  
		char S[maxn];
		scanf("%s",S);
		memset(val,0,sizeof(val));
		int lenS=strlen(S); 
		int j=0;
		for(int i=lenS-1;i>=0;i-=7){
			int t=max(i-6,0),res=0;
			while(t<=i){
				res=res*10+S[t]-'0';
				t++;
			}
			val[++j]=res;
		}
		val[0]=j;
	}
	
	/*inline void StrIn(char *S){
		memset(val,0,sizeof(val));
		int lenS=strlen(S);
		val[0]=lenS;
		for(int i=lenS-1,j=1;i>=0;i--,j++) val[j]=S[i]-'0';
	}*/
	
	inline void output(){ // 输出  
		printf("%ld",val[val[0]]);
		for(int i=val[0]-1;i>=1;i--)
		 printf("%07ld",val[i]); 
	}
	
	bool operator ==(const largenum &obj)const{ // 判断是否等于  
		if(val[0]!=obj[0]) return false;
		for(int i=1;i<=val[0];i++) if(val[i]!=obj[i]) return false;
		return true;
	}
	
	bool operator <(const largenum &obj)const{ // 判断是否小于   
		if(val[0]>obj[0]) return false;
		if((*this)==obj) return false;
		if(val[0]<obj[0]) return true;
		for(int i=val[0];i>=1;i--){
			if(val[i]>obj[i]) return false;
			if(val[i]<obj[i]) return true;
		}
		return true;
	}
	
	bool operator >(const largenum &obj)const{ // 判断是否大于   
		largenum cmp=*this;
		if(cmp < obj || cmp == obj) return false;
		return true;
	}
	
	largenum operator +(const largenum &obj)const{ // 加法运算  
		largenum cmp;
		memset(cmp.val,0,sizeof(cmp.val));
		Int64 pos=max(val[0],obj.val[0]),add=0;
		for(int i=1;i<=pos;i++){
			cmp.val[i]=val[i]+obj[i]+add;
			add=cmp.val[i]/carries;
			cmp.val[i]=cmp.val[i]%carries;
		}
		if(add>0) cmp.val[++pos]=add;
		cmp.val[0]=pos;
		return cmp;
	}
	
	largenum operator -(const largenum &obj)const{ // 减法运算 只能减出正数  
		largenum cmp;
		memset(cmp.val,0,sizeof(cmp.val));
		Int64 pos=val[0],rent=0; // rent 借位  
		for(int i=1;i<=pos;i++){
			cmp.val[i]=val[i]-obj[i]-rent;
			if(cmp.val[i]<0) {cmp.val[i]+=carries;rent=1;}
			else rent=0;
		}
		while(cmp.val[pos]==0 && pos>1) pos--;
		cmp.val[0]=pos;
		return cmp;
	}
	
	largenum operator *(const int &obj)const{ // 高精度 ×低精度 
		
		largenum cmp;
		memset(cmp.val,0,sizeof(cmp.val));
		Int64 pos=val[0]; // 进位 
		long long add=0;
		for(int i=1;i<=pos;i++){
			cmp.val[i]=val[i]*obj+add;
			add=cmp.val[i]/carries;
			cmp.val[i]=cmp.val[i]%carries;
		}
		while(add>0){
			cmp.val[++pos]=add%carries;
			add/=carries;
		}
		while(cmp.val[pos]==0 && pos>1) pos--;
		cmp.val[0]=pos;
		return cmp;
	}
	
	largenum operator *(const largenum &obj)const{ // 高精度 ×高精度 
		// 对于高精度数 a 和高精度 b   
		// 这个算法不能写成 a=a*b 
		largenum cmp;
		memset(cmp.val,0,sizeof(cmp.val));
		Int64 pos=val[0]+obj[0];
		for(int i=1;i<=val[0];i++){
			for(int j=1;j<=obj[0];j++){
				cmp.val[i+j-1]+=val[i]*obj[j];
				cmp.val[i+j]+=cmp.val[i+j-1]/carries;
				cmp.val[i+j-1]=cmp.val[i+j-1]%carries;
			}
		}
		while(cmp.val[pos]==0 && pos>1) pos--;
		cmp.val[0]=pos;
		return cmp;
	}
	
	largenum operator /(const int &obj)const{ // 高精度 ÷低精度  
		largenum cmp;
		memset(cmp.val,0,sizeof(cmp.val));
		Int64 pos=val[0],div=0;
		for(int i=pos;i>=1;i--){
			cmp.val[i]=(div*carries+val[i])/obj;
			div=(div*carries+val[i])%obj;
		}
		while(cmp[pos]==0 && pos>1) pos--;
		cmp.val[0]=pos;
		return cmp;
	}
	
	int operator %(const int &obj)const{ // 高精度 % 低精度  
		int pos=val[0],div=0;
		for(int i=pos;i>=1;i--) div=(div*carries+val[i])%obj;
		return div;
	}
	
	largenum operator /(const largenum &obj)const{ // 高精度 ÷高精度  
		largenum cmp,t_cmp;
		memset(cmp.val,0,sizeof(cmp.val));
		memset(t_cmp.val,0,sizeof(t_cmp.val));
		Int64 pos=val[0];
		cmp.val[0]=1;cmp.val[1]=0;
		t_cmp=cmp;
		if((*this)<obj) return cmp; // 小于除数直接返回 0  
		for(int i=pos;i>=1;i--){
			t_cmp=t_cmp*carries;
			t_cmp.val[1]=val[i];
			int k=0;
			while(t_cmp>obj || t_cmp==obj)
			{
				t_cmp=t_cmp-obj;
				k++;
			}
			cmp.val[i]=k;
		}
		while(cmp.val[pos]==0 && pos>1) pos--;
		cmp.val[0]=pos;
		return cmp;
	}
	
	largenum operator %(const largenum &obj)const{ // 高精度 % 高精度  
		largenum t_cmp;
		memset(t_cmp.val,0,sizeof(t_cmp.val));
		Int64 pos=val[0];
		t_cmp.val[0]=1;t_cmp.val[1]=0;
		if((*this)<obj) return (*this); // 小于除数直接返回本身 
		for(int i=pos;i>=1;i--){
			t_cmp=t_cmp*carries;
			t_cmp.val[1]=val[i];
			while(t_cmp>obj || t_cmp==obj) t_cmp=t_cmp-obj;
		}
		return t_cmp;
	}
	void lgnsqrt(){
		largenum one={{1,1}};
		largenum l={{1,1}};
		largenum r=*this;
		largenum cmp=*this;
		largenum mid=(l+r)/2;
		largenum tmp=mid*mid;
		while(l<r){
			if(tmp<cmp||tmp==cmp){
				l=mid+one;
			}
			else r=mid;
 			mid=(l+r)/2;
			tmp=mid*mid;
		}
		if(mid*mid>cmp&&((mid-one)*(mid-one)<cmp||(mid-one)*(mid-one)==cmp))
			mid=mid-one;
		for(int i=0;i<=mid.val[0];i++){
			val[i]=mid.val[i];
		}
	}

在这一段高精度的最后是自己写的二分开方这里就按正常的开方来就可以了，因为是向下取整，所以呢我就在在后面加了一个if语句。
那么，That’s all.

  1. 1. 压位的原因
  2. 2. 例题引入