今天我刷题了吗
搜索文档…
高精度
1
#define MAXLEN 10010
2
#define MAXN 9999
3
#define MAXSIZE 1010
4
#define DLEN 4
5
6
class BigNum
7
{
8
private:
9
int a[MAXLEN];
10
int len;
11
public:
12
BigNum() { len = 1; memset(a, 0, sizeof(a)); }
13
BigNum(const int);
14
BigNum(const char*);
15
BigNum(const BigNum&);
16
BigNum& operator =(const BigNum &);
17
friend istream& operator >>(istream&, BigNum&);
18
friend ostream& operator <<(ostream&, BigNum&);
19
BigNum operator +(const BigNum&) const;
20
BigNum operator -(const BigNum&) const;
21
BigNum operator *(const BigNum&) const;
22
BigNum operator /(const int&) const;
23
BigNum operator ^(const int&) const;
24
int operator %(const int&) const;
25
bool operator >(const BigNum& T)const;
26
bool operator >(const int& t)const;
27
void print();
28
};
29
30
BigNum::BigNum(const int b)
31
{
32
int c, d = b;
33
len = 0;
34
memset(a, 0, sizeof(a));
35
while (d > MAXN)
36
{
37
c = d - (d / (MAXN + 1)) * (MAXN + 1);
38
d = d / (MAXN + 1);
39
a[len++] = c;
40
}
41
a[len++] = d;
42
}
43
44
BigNum::BigNum(const char* s)
45
{
46
int t, k, index, L, i;
47
memset(a, 0, sizeof(a));
48
L = (int)strlen(s);
49
len = L / DLEN;
50
if (L % DLEN) len++;
51
index = 0;
52
for (i = L - 1; i >= 0; i -= DLEN)
53
{
54
t = 0;
55
k = i - DLEN + 1;
56
if (k < 0) k = 0;
57
for (int j = k; j <= i; j++)
58
t = t * 10 + s[j] - '0';
59
a[index++] = t;
60
}
61
}
62
63
BigNum::BigNum(const BigNum& T) : len(T.len)
64
{
65
int i;
66
memset(a, 0, sizeof(a));
67
for (i = 0; i < len; i++) a[i] = T.a[i];
68
}
69
70
BigNum& BigNum::operator =(const BigNum& n)
71
{
72
int i;
73
len = n.len;
74
memset(a, 0, sizeof(a));
75
for (i = 0; i < len; i++) a[i] = n.a[i];
76
return *this;
77
}
78
79
istream& operator >>(istream& in, BigNum& b)
80
{
81
char ch[MAXSIZE * 4];
82
int i = -1;
83
in >> ch;
84
int L = (int)strlen(ch);
85
int count = 0, sum = 0;
86
for (i = L - 1; i >= 0;)
87
{
88
sum = 0;
89
int t = 1;
90
for (int j = 0; j < 4 && i >= 0; j++, i--, t *= 10)
91
sum += (ch[i] - '0') * t;
92
b.a[count] = sum;
93
count++;
94
}
95
b.len = count++;
96
return in;
97
}
98
99
ostream& operator <<(ostream& out, BigNum& b)
100
{
101
int i;
102
cout << b.a[b.len - 1];
103
for (i = b.len - 2; i >= 0; i--)
104
printf("%04d", b.a[i]);
105
return out;
106
}
107
108
BigNum BigNum::operator +(const BigNum& T) const
109
{
110
BigNum t(*this);
111
int i, big;
112
big = T.len > len ? T.len : len;
113
for (i = 0; i < big; i++)
114
{
115
t.a[i] += T.a[i];
116
if (t.a[i] > MAXN)
117
{
118
t.a[i + 1]++;
119
t.a[i] -= MAXN + 1;
120
}
121
}
122
if (t.a[big] != 0) t.len = big + 1;
123
else t.len = big;
124
return t;
125
}
126
127
BigNum BigNum::operator -(const BigNum& T) const
128
{
129
int i, j, big;
130
bool flag;
131
BigNum t1, t2;
132
if (*this > T)
133
{
134
t1 = *this;
135
t2 = T;
136
flag = 0;
137
}
138
else
139
{
140
t1 = T;
141
t2 = *this;
142
flag = 1;
143
}
144
big = t1.len;
145
for (i = 0; i < big; i++)
146
{
147
if (t1.a[i] < t2.a[i])
148
{
149
j = i + 1;
150
while (t1.a[j] == 0) j++;
151
t1.a[j--]--;
152
while (j > i) t1.a[j--] += MAXN;
153
t1.a[i] += MAXN + 1 - t2.a[i];
154
}
155
else t1.a[i] -= t2.a[i];
156
}
157
t1.len = big;
158
while (t1.a[t1.len - 1] == 0 && t1.len > 1)
159
{
160
t1.len--;
161
big--;
162
}
163
if (flag) t1.a[big - 1] = 0 - t1.a[big - 1];
164
return t1;
165
}
166
167
BigNum BigNum::operator *(const BigNum& T)const
168
{
169
BigNum ret;
170
int i, j = 0, up;
171
int temp, temp1;
172
for (i = 0; i < len; i++)
173
{
174
up = 0;
175
for (j = 0; j < T.len; j++)
176
{
177
temp = a[i] * T.a[j] + ret.a[i + j] + up;
178
if (temp > MAXN)
179
{
180
temp1 = temp - temp / (MAXN + 1) * (MAXN + 1);
181
up = temp / (MAXN + 1);
182
ret.a[i + j] = temp1;
183
}
184
else
185
{
186
up = 0;
187
ret.a[i + j] = temp;
188
}
189
}
190
if (up != 0) ret.a[i + j] = up;
191
}
192
ret.len = i + j;
193
while (ret.a[ret.len - 1] == 0 && ret.len > 1) ret.len--;
194
return ret;
195
}
196
197
BigNum BigNum::operator /(const int& b)const
198
{
199
BigNum ret;
200
int i, down = 0;
201
for (i = len - 1; i >= 0; i--)
202
{
203
ret.a[i] = (a[i] + down * (MAXN + 1)) / b;
204
down = a[i] + down * (MAXN + 1) - ret.a[i] * b;
205
}
206
ret.len = len;
207
while (ret.a[ret.len - 1] == 0 && ret.len > 1) ret.len--;
208
return ret;
209
}
210
211
int BigNum::operator %(const int& b) const
212
{
213
int i, d = 0;
214
for (i = len - 1; i >= 0; i--)
215
d = ((d * (MAXN + 1)) % b + a[i]) % b;
216
return d;
217
}
218
219
BigNum BigNum::operator ^(const int& n) const
220
{
221
BigNum t, ret(1);
222
int i;
223
if (n < 0) exit(-1);
224
if (n == 0) return 1;
225
if (n == 1) return *this;
226
int m = n;
227
while (m > 1)
228
{
229
t = *this;
230
for (i = 1; (i << 1) <= m; i <<= 1) t = t * t;
231
m -= i;
232
ret = ret * t;
233
if (m == 1) ret = ret * (*this);
234
}
235
return ret;
236
}
237
238
bool BigNum::operator >(const BigNum& T) const
239
{
240
int ln;
241
if (len > T.len) return true;
242
else if (len == T.len)
243
{
244
ln = len - 1;
245
while (a[ln] == T.a[ln] && ln >= 0) ln--;
246
if (ln >= 0 && a[ln] > T.a[ln]) return true;
247
else return false;
248
}
249
else return false;
250
}
251
252
bool BigNum::operator >(const int& t) const
253
{
254
BigNum b(t);
255
return *this > b;
256
}
257
258
void BigNum::print()
259
{
260
int i;
261
printf("%d", a[len - 1]);
262
for (i = len - 2; i >= 0; i--)
263
printf("%04d", a[i]);
264
printf("\n");
265
}
Copied!
最近更新 1yr ago
复制链接