【OI之路】02数论算法-7高精度

基本功:高精度

很久以前写的,变量名可能不甚雅观,还请见谅

Mine

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
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
#ifndef HPC_H
#define HPC_H
#include<cstring>
#include<sstream>
#include<string>
using namespace std;
bool error;
//-------------------------↓类型定义-------------------------
struct fuk
{
int len,num[50];
bool isf;
fuk()
{
len=0;
memset(num,0,sizeof(num));
isf=false;
}
};
//-------------------------↑类型定义-------------------------
//-------------------------↓转换函数-------------------------
string inttostr(int a)
{
//return boost::lexical_cast<string>(a);
stringstream ss;ss<<a;
string s;ss>>s;
return s;
}
int strtoint(string s)
{
//return boost::lexical_cast<int>(s);
stringstream ss;ss<<s;
int i;ss>>i;
return i;
}
fuk strtofuk(string s)
{
fuk f;
f.len=s.size();
for(int i=1;i<=f.len;i++) f.num[f.len-i+1]=s[i-1]-'0';
return f;
}
string fuktostr(fuk f)
{
string s="";
for(int i=f.len;i>=1;i--) s=s+inttostr(f.num[i]);
return s;
}
fuk inttofuk(int a)
{
return strtofuk(inttostr(a));
}
void fswap(fuk *a,fuk *b)
{
fuk p;
p=*a;
*a=*b;
*b=p;
}
//-------------------------↑转换函数-------------------------
//-------------------------↓比较函数-------------------------
int maxer(int x,int y)
{
return x>y?x:y;
}
int miner(int x,int y)
{
return x>y?y:x;
}
//相等返回0,大于返回1,小于返回-1
int fcmp(fuk a,fuk b)
{
if( a.isf==true and b.isf==false ) return -1;
if( a.isf==false and b.isf==true ) return 1;
if( a.isf==true and b.isf==true ) fswap(&a,&b);
if(a.len>b.len) return 1;
if(a.len<b.len) return -1;
int i=a.len;
while(a.num[i]==b.num[i] and i>0) i--;
if(i==0) return 0;
if(a.num[i]>b.num[i]) return 1;
else return -1;
}
fuk fmax(fuk a,fuk b)
{
if(fcmp(a,b)==1) return a;
else return b;
}
fuk fmin(fuk a,fuk b)
{
if(fcmp(a,b)==-1) return a;
else return b;
}
int is0(fuk a)//-1 => a<0 0 => a=0 1 => a>0
{
if(a.len==1 and a.num[1]==0) return 0;
if(a.isf==true) return -1;
return 1;
}
//-------------------------↑比较函数-------------------------
fuk h_add_i(fuk a,fuk b)
{
fuk c;
c.len=maxer(a.len,b.len);
for(int i=1; i<=c.len; i++)
c.num[i]=a.num[i]+b.num[i];
for(int i=1; i<=c.len; i++)
{
c.num[i+1]+=c.num[i]/10;
c.num[i]%=10;
}
int i=c.len;
while(c.num[i+1]>0)
{
i++;
c.num[i+1]=c.num[i+1]+c.num[i]/10;
c.num[i]=c.num[i]%10;
}
while(c.num[i]==0 and i>1) i--;
c.len=i;
return c;
}
fuk h_add_l(fuk a,int b)
{
a.num[1]+=b;
for(int i=1; i<=a.len; i++)
{
a.num[i+1]+=a.num[i]/10;
a.num[i]%=10;
}
int i=a.len;
while(a.num[i+1]>0)
{
i++;
a.num[i+1]=a.num[i+1]+a.num[i]/10;
a.num[i]=a.num[i]%10;
}
while(a.num[i]==0 and i>1) i--;
a.len=i;
return a;
}
fuk h_sub_i(fuk a,fuk b)
{
fuk c;
int t=fcmp(a,b);
if( t==0 )
{
c=strtofuk("0");
return c;
}
if( t==-1 )
{
fswap(&a,&b);
c.isf=true;
}
c.len=a.len;
for(int i=1;i<=c.len;i++)
c.num[i]=a.num[i]-b.num[i];
for(int i=1;i<=c.len;i++)
if(c.num[i]<0)
{
c.num[i]+=10;
c.num[i+1]--;
}
int i=c.len;
while(c.num[i+1]>0)
{
i++;
c.num[i+1]=c.num[i+1]+c.num[i]/10;
c.num[i]=c.num[i]%10;
}
while ( c.num[i]==0 and i>1) i--;
c.len=i;
return c;
}
fuk h_mul_l(fuk xx,int y)
{
fuk ans;
ans.len=xx.len;
for(int i=1; i<=ans.len; i++)
ans.num[i]+=xx.num[i]*y;
for(int i=1; i<=ans.len; i++)
{
ans.num[i+1]+=ans.num[i]/10;
ans.num[i]%=10;
}
int i=ans.len;
while(ans.num[i+1]>0)
{
i++;
ans.num[i+1]+=ans.num[i]/10;
ans.num[i]%=10;
}
while(ans.num[i]==0 and i>0) i--;
ans.len=i;
return ans;
}
fuk h_mul_i(fuk a,fuk b)
{
fuk c;
c.len=a.len+b.len+1;
for(int i=1; i<=a.len; i++)
for(int j=1; j<=b.len; j++)
c.num[i+j-1]=c.num[i+j-1]+a.num[i]*b.num[j];
for(int i=1; i<=c.len; i++)
{
c.num[i+1]=c.num[i+1]+c.num[i]/10;
c.num[i]=c.num[i]%10;
}
int i=c.len;
while(c.num[i+1]>0)
{
i++;
c.num[i+1]=c.num[i+1]+c.num[i]/10;
c.num[i]=c.num[i]%10;
}
while(c.num[i]==0 and i>1) i--;
c.len=i;
return c;
}
fuk h_div_i(fuk a,fuk b)
{
fuk ans=strtofuk("0");
if(is0(b)==0)
{
error=true;
return ans;
}
if(is0(a)==0) return ans;//0
int t=fcmp(a,b);
if(t<0) return ans;//0
if(t==0) return strtofuk("1");
fuk d=strtofuk("0");
int pos=0;
while(pos<a.len)
{
if(fcmp(d,b)<0)
{
pos++;
d=h_add_l(h_mul_l(d,10),a.num[a.len-pos+1]);
}
ans=h_mul_l(ans,10);
int k=0;
while(fcmp(d,b)>=0)
{
d=h_sub_i(d,b);
k++;
}
ans=h_add_l(ans,k);
}
return ans;
}
//外部接口
string h_add(string a,string b)
{
return fuktostr(h_add_i(strtofuk(a),strtofuk(b)));
}
string h_sub(string a,string b)
{
return fuktostr(h_sub_i(strtofuk(a),strtofuk(b)));
}
string h_mul(string a,string b)
{
return fuktostr(h_mul_i(strtofuk(a),strtofuk(b)));
}
string h_mul2(string a,int b)
{
return fuktostr(h_mul_l(strtofuk(a),b));
}
string h_div(string a,string b)
{
error=false;
fuk c=h_div_i(strtofuk(a),strtofuk(b));
if(error==true) return "不能被0除";
return fuktostr(c);
}
#endif

可参考

1.

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
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
#ifndef HPC_H
#define HPC_H
#include<iosfwd>
#include<cstring>
#include<string>
using namespace std;
#define MAX_L_HPC 500 //最大长度,可以修改
class hpc
{
public:
int len,s[MAX_L_HPC];//数的长度,记录数组
bool sign;//符号 1正数 0负数
//构造函数
hpc();//初始化
hpc(const char*);
hpc(const string);
hpc(const int);//强制转换
string tostr() const;//转化为字符串
friend istream& operator>>(istream &,hpc &);//重载输入流
friend ostream& operator<<(ostream &,hpc &);//重载输出流
//重载赋值
hpc operator=(const char*);
hpc operator=(const int);
hpc operator=(const string);
//重载各种比较
bool operator>(const hpc &) const;
bool operator>=(const hpc &) const;
bool operator<(const hpc &) const;
bool operator<=(const hpc &) const;
bool operator==(const hpc &) const;
bool operator!=(const hpc &) const;
//重载四则运算
hpc operator+(const hpc &) const;
hpc operator++();
hpc operator++(int);
hpc operator+=(const hpc&);
hpc operator-(const hpc &) const;
hpc operator--();
hpc operator--(int);
hpc operator-=(const hpc&);
hpc operator*(const hpc &)const;
hpc operator*(const int num)const;
hpc operator*=(const hpc&);
hpc operator/(const hpc&)const;
hpc operator/=(const hpc&);
//四则运算的衍生运算
hpc operator%(const hpc&)const;//取模(余数)
hpc factorial()const;//阶乘
hpc sqrt() const;//整数开根(向下取整)
hpc pow(const hpc&)const;//次方
//一些乱乱的函数
void clean();//退位
hpc abs() const;
};
//-------------------------
void hpcswap(hpc *a,hpc *b) {hpc p=*a;*a=*b;*b=p;}
int maxer(int x,int y) {return x>y?x:y;}
int miner(int x,int y) {return x>y?y:x;}
//-------------------------
hpc::hpc()
{
memset(s,0,sizeof(s));
len=1;
sign=true;
}
hpc::hpc(const char *num) {*this=num;}
hpc::hpc(const string num) {*this=num;}
hpc::hpc(const int num) {*this=num;}
//链接到=
string hpc::tostr() const
{
string res="";
for(int i=0;i<len;i++) res=char(s[i]+'0')+res;
if(res=="") res="0";
if(sign==false and res!="0") res="-"+res;
return res;
}
istream &operator>>(istream &in,hpc &num)
{
string str;
in>>str;
num=str;
return in;
}
ostream &operator<<(ostream &out, hpc &num)
{
out<<num.tostr();
return out;
}
hpc hpc::operator=(const char *num)
{
memset(s,0,sizeof(s));
char a[MAX_L_HPC]="";
if(num[0]!='-') strcpy(a,num);
else for(int i=1;i<strlen(num);i++) a[i-1]=num[i];
sign=(num[0]!='-');
len=strlen(a);
for(int i=0;i<strlen(a);i++) s[i]=a[len-i-1]-'0';
return *this;
}
hpc hpc::operator=(int num)
{
if(num<0) sign=false,num=-num;
else sign=true;
char temp[MAX_L_HPC];
sprintf(temp,"%d",num);
*this=temp;
return *this;
}
hpc hpc::operator=(const string s)
{
*this=s.c_str();
return *this;
}
bool hpc::operator<(const hpc &num) const
{
if(sign^num.sign) return num.sign;
if(len!=num.len) return len<num.len;//巧妙!
int i=len;
while(s[i]==num.s[i] and i>0) i--;
if(i==0) return false;
return s[i]<num.s[i];
}
bool hpc::operator>(const hpc&num)const {return num<*this;}
bool hpc::operator<=(const hpc&num)const {return !(*this>num);}
bool hpc::operator>=(const hpc&num)const {return !(*this<num);}
bool hpc::operator!=(const hpc&num)const {return *this>num or *this<num;}
bool hpc::operator==(const hpc&num)const {return !(num!=*this);}
hpc hpc::operator+(const hpc &b) const
{
if (sign^b.sign)
{
if(sign) return *this-b.abs();
else return b-abs();
}
//已知:a,b>=0
hpc c;c.len=maxer(len,b.len);c.sign=sign;
for(int i=1;i<=c.len;i++) c.s[i]=s[i]+b.s[i];
/*for(int i=1;i<=c.len;i++) c.s[i+1]+=c.s[i]/10,c.s[i]%=10;
int i=c.len;
while(c.s[i+1]>0) {i++;c.s[i+1]+=c.s[i]/10;c.s[i]%=10;}
while(c.s[i]==0 and i>1) i--;
c.len=i;*/
c.clean();
return c;
}
hpc hpc::operator++()
{
*this=*this+1;
return *this;
}
hpc hpc::operator++(int)
{
hpc old=*this;
++(*this);
return old;
}
hpc hpc::operator+=(const hpc &num)
{
*this=*this+num;
return *this;
}
hpc hpc::operator-(const hpc &num) const
{
hpc a=*this,b=num;
if(a==b) return 0;
if(b.sign==sign==false) return b.abs()-a.abs();
if(b.sign==false) return a+b.abs();
if(a.sign==false) return hpc(0)-(a.abs()+b);
if(a<b) return hpc(0)-(b-a);
//已知:a,b>=0;a>b
hpc c;c.len=a.len;
for(int i=1;i<=c.len;i++) c.num[i]=a.num[i]-b.num[i];
for(int i=1;i<=c.len;i++)
if(c.num[i]<0)
{
c.num[i]+=10;
c.num[i+1]--;
}
int i=c.len;
while(c.num[i+1]>0)
{
i++;
c.num[i+1]=c.num[i+1]+c.num[i]/10;
c.num[i]=c.num[i]%10;
}
while ( c.num[i]==0 and i>1) i--;
c.len=i;
return c;
}
hpc hpc::operator * (const hpc &num)const
{
hpc result;
result.len = len + num.len;
for (int i = 0; i < len; i++)
for (int j = 0; j < num.len; j++)
result.s[i + j] += s[i] * num.s[j];
for (int i = 0; i < result.len; i++)
{
result.s[i + 1] += result.s[i] / 10;
result.s[i] %= 10;
}
result.clean();
result.sign = !(sign^num.sign);
return result;
}
hpc hpc::operator*(const int num)const
{
hpc x = num;
hpc z = *this;
return x*z;
}
hpc hpc::operator*=(const hpc&num)
{
*this = *this * num;
return *this;
}
hpc hpc::operator /(const hpc&num)const
{
hpc ans;
ans.len = len - num.len + 1;
if (ans.len < 0)
{
ans.len = 1;
return ans;
}
hpc divisor = *this, divid = num;
divisor.sign = divid.sign = 1;
int k = ans.len - 1;
int j = len - 1;
while (k >= 0)
{
while (divisor.s[j] == 0) j--;
if (k > j) k = j;
char z[MAX_L_HPC];
memset(z, 0, sizeof(z));
for (int i = j; i >= k; i--)
z[j - i] = divisor.s[i] + '0';
hpc dividend = z;
if (dividend < divid)
{
k--;
continue;
}
int key = 0;
while (divid*key <= dividend) key++;
key--;
ans.s[k] = key;
hpc temp = divid*key;
for (int i = 0; i < k; i++)
temp = temp * 10;
divisor = divisor - temp;
k--;
}
ans.clean();
ans.sign = !(sign^num.sign);
return ans;
}
hpc hpc::operator/=(const hpc&num)
{
*this = *this / num;
return *this;
}
hpc hpc::operator%(const hpc& num)const
{
hpc a = *this, b = num;
a.sign = b.sign = 1;
hpc result, temp = a / b*b;
result = a - temp;
result.sign = sign;
return result;
}
hpc hpc::pow(const hpc& num)const
{
hpc result = 1;
for (hpc i = 0; i < num; i++)
result = result*(*this);
return result;
}
hpc hpc::factorial()const
{
hpc result = 0;
++result;
for (hpc i = 1; i <= *this; i++)
result *= i;
return result;
}
hpc hpc::sqrt()const
{
if(*this<0)return -1;
if(*this<=1)return *this;
hpc l=0,r=*this,mid;
while(r-l>1)
{
mid=(l+r)/2;
if(mid*mid>*this)
r=mid;
else
l=mid;
}
return l;
}
void hpc::clean()//退位
{
int i=len;
for(int i=1;i<=len;i++)
{
s[i+1]+=s[i]/10;s[i]%=10;
if(s[i]<0) {s[i]+=10;s[i+1]--;}
}
while(s[i+1]>0) {i++;s[i+1]+=s[i]/10;s[i]%=10;}
while(s[i]==0 and i>1) i--;
len=i;
}
hpc hpc::abs() const
{
hpc t=*this;
t.sign=true;
return t;
}
#endif

另一个

这里

本文基于 知识共享署名-相同方式共享 4.0 国际许可协议发布
本文地址:http://zory.cf/posts/9163.html
转载请注明出处,谢谢!

哪怕是一杯奶茶,也将鼓励我继续创作!
0%