1 //作者：小黑AWM+MashPlant
2 //注：可以直接把BigInt和一样用cin cout都行，就是高精乘为了速度才用了FFT降低了精度，有需要可以自行更改。
3 #include <cstdio>
4 #include <iostream>
5 #include <cmath>
6 #include <string>
7 #include <cstring>
8 #include <vector>
9 #include <algorithm>
10 using namespace std;
11 const double PI = acos(-1.0);
12 struct Complex{
13 double x,y;
14 Complex(double _x = 0.0,double _y = 0.0){
15 x = _x;
16 y = _y;
17 }
18 Complex operator-(const Complex &b)const{
19 return Complex(x - b.x,y - b.y);
20 }
21 Complex operator+(const Complex &b)const{
22 return Complex(x + b.x,y + b.y);
23 }
24 Complex operator*(const Complex &b)const{
25 return Complex(x*b.x - y*b.y,x*b.y + y*b.x);
26 }
27 };
28 void change(Complex y[],int len){
29 int i,j,k;
30 for(int i = 1,j = len/2;i<len-1;i++){
31 if(i < j) swap(y[i],y[j]);
32 k = len/2;
33 while(j >= k){
34 j = j - k;
35 k = k/2;
36 }
37 if(j < k) j+=k;
38 }
39 }
40 void fft(Complex y[],int len,int on){
41 change(y,len);
42 for(int h = 2;h <= len;h<<=1){
43 Complex wn(cos(on*2*PI/h),sin(on*2*PI/h));
44 for(int j = 0;j < len;j += h){
45 Complex w(1,0);
46 for(int k = j;k < j + h/2;k++){
47 Complex u = y[k];
48 Complex t = w*y[k + h/2];
49 y[k] = u + t;
50 y[k + h/2] = u - t;
51 w = w*wn;
52 }
53 }
54 }
55 if(on == -1){
56 for(int i = 0;i < len;i++){
57 y[i].x /= len;
58 }
59 }
60 }
61 class BigInt
62 {
63 #define Value(x, nega) ((nega) ? -(x) : (x))
64 #define At(vec, index) ((index) < vec.size() ? vec[(index)] : 0)
65 static int absComp(const BigInt &lhs, const BigInt &rhs)
66 {
67 if (lhs.size() != rhs.size())
68 return lhs.size() < rhs.size() ? -1 : 1;
69 for (int i = lhs.size() - 1; i >= 0; --i)
70 if (lhs[i] != rhs[i])
71 return lhs[i] < rhs[i] ? -1 : 1;
72 return 0;
73 }
74 using Long = long long;
75 const static int Exp = 9;
76 const static Long Mod = 1000000000;
77 mutable std::vector<Long> val;
78 mutable bool nega = false;
79 void trim() const
80 {
81 while (val.size() && val.back() == 0)
82 val.pop_back();
83 if (val.empty())
84 nega = false;
85 }
86 int size() const { return val.size(); }
87 Long &operator[](int index) const { return val[index]; }
88 Long &back() const { return val.back(); }
89 BigInt(int size, bool nega) : val(size), nega(nega) {}
90 BigInt(const std::vector<Long> &val, bool nega) : val(val), nega(nega) {}
91
92 public:
93 friend std::ostream &operator<<(std::ostream &os, const BigInt &n)
94 {
95 if (n.size())
96 {
97 if (n.nega)
98 putchar('-');
99 for (int i = n.size() - 1; i >= 0; --i)
100 {
101 if (i == n.size() - 1)
102 printf("%lld", n[i]);
103 else
104 printf("%0*lld", n.Exp, n[i]);
105 }
106 }
107 else
108 putchar('0');
109 return os;
110 }
111 friend BigInt operator+(const BigInt &lhs, const BigInt &rhs)
112 {
113 BigInt ret(lhs);
114 return ret += rhs;
115 }
116 friend BigInt operator-(const BigInt &lhs, const BigInt &rhs)
117 {
118 BigInt ret(lhs);
119 return ret -= rhs;
120 }
121 BigInt(Long x = 0)
122 {
123 if (x < 0)
124 x = -x, nega = true;
125 while (x >= Mod)
126 val.push_back(x % Mod), x /= Mod;
127 if (x)
128 val.push_back(x);
129 }
130 BigInt(const char *s)
131 {
132 int bound = 0, pos;
133 if (s[0] == '-')
134 nega = true, bound = 1;
135 Long cur = 0, pow = 1;
136 for (pos = strlen(s) - 1; pos >= Exp + bound - 1; pos -= Exp, val.push_back(cur), cur = 0, pow = 1)
137 for (int i = pos; i > pos - Exp; --i)
138 cur += (s[i] - '0') * pow, pow *= 10;
139 for (cur = 0, pow = 1; pos >= bound; --pos)
140 cur += (s[pos] - '0') * pow, pow *= 10;
141 if (cur)
142 val.push_back(cur);
143 }
144 BigInt &operator=(const char *s){
145 BigInt n(s);
146 *this = n;
147 return n;
148 }
149 BigInt &operator=(const Long x){
150 BigInt n(x);
151 *this = n;
152 return n;
153 }
154 friend std::istream &operator>>(std::istream &is, BigInt &n){
155 string s;
156 is >> s;
157 n=(char*)s.data();
158 return is;
159 }
160 BigInt &operator+=(const BigInt &rhs)
161 {
162 const int cap = std::max(size(), rhs.size()) + 1;
163 val.resize(cap);
164 int carry = 0;
165 for (int i = 0; i < cap - 1; ++i)
166 {
167 val[i] = Value(val[i], nega) + Value(At(rhs, i), rhs.nega) + carry, carry = 0;
168 if (val[i] >= Mod)
169 val[i] -= Mod, carry = 1;
170 else if (val[i] < 0)
171 val[i] += Mod, carry = -1;
172 }
173 if ((val.back() = carry) == -1) //assert(val.back() == 1 or 0 or -1)
174 {
175 nega = true, val.pop_back();
176 bool tailZero = true;
177 for (int i = 0; i < cap - 1; ++i)
178 {
179 if (tailZero && val[i])
180 val[i] = Mod - val[i], tailZero = false;
181 else
182 val[i] = Mod - 1 - val[i];
183 }
184 }
185 trim();
186 return *this;
187 }
188 friend BigInt operator-(const BigInt &rhs)
189 {
190 BigInt ret(rhs);
191 ret.nega ^= 1;
192 return ret;
193 }
194 BigInt &operator-=(const BigInt &rhs)
195 {
196 rhs.nega ^= 1;
197 *this += rhs;
198 rhs.nega ^= 1;
199 return *this;
200 }
201 friend BigInt operator*(const BigInt &lhs, const BigInt &rhs)
202 {
203 int len=1;
204 BigInt ll=lhs,rr=rhs;
205 ll.nega = lhs.nega ^ rhs.nega;
206 while(len<2*lhs.size()||len<2*rhs.size())len<<=1;
207 ll.val.resize(len),rr.val.resize(len);
208 Complex x1[len],x2[len];
209 for(int i=0;i<len;i++){
210 Complex nx(ll[i],0.0),ny(rr[i],0.0);
211 x1[i]=nx;
212 x2[i]=ny;
213 }
214 fft(x1,len,1);
215 fft(x2,len,1);
216 for(int i = 0 ; i < len; i++)
217 x1[i] = x1[i] * x2[i];
218 fft( x1 , len , -1 );
219 for(int i = 0 ; i < len; i++)
220 ll[i] = int( x1[i].x + 0.5 );
221 for(int i = 0 ; i < len; i++){
222 ll[i+1]+=ll[i]/Mod;
223 ll[i]%=Mod;
224 }
225 ll.trim();
226 return ll;
227 }
228 friend BigInt operator*(const BigInt &lhs, const Long &x){
229 BigInt ret=lhs;
230 bool negat = ( x < 0 );
231 Long xx = (negat) ? -x : x;
232 ret.nega ^= negat;
233 ret.val.push_back(0);
234 ret.val.push_back(0);
235 for(int i = 0; i < ret.size(); i++)
236 ret[i]*=xx;
237 for(int i = 0; i < ret.size(); i++){
238 ret[i+1]+=ret[i]/Mod;
239 ret[i] %= Mod;
240 }
241 ret.trim();
242 return ret;
243 }
244 BigInt &operator*=(const BigInt &rhs) { return *this = *this * rhs; }
245 BigInt &operator*=(const Long &x) { return *this = *this * x; }
246 friend BigInt operator/(const BigInt &lhs, const BigInt &rhs)
247 {
248 static std::vector<BigInt> powTwo{BigInt(1)};
249 static std::vector<BigInt> estimate;
250 estimate.clear();
251 if (absComp(lhs, rhs) < 0)
252 return BigInt();
253 BigInt cur = rhs;
254 int cmp;
255 while ((cmp = absComp(cur, lhs)) <= 0)
256 {
257 estimate.push_back(cur), cur += cur;
258 if (estimate.size() >= powTwo.size())
259 powTwo.push_back(powTwo.back() + powTwo.back());
260 }
261 if (cmp == 0)
262 return BigInt(powTwo.back().val, lhs.nega ^ rhs.nega);
263 BigInt ret = powTwo[estimate.size() - 1];
264 cur = estimate[estimate.size() - 1];
265 for (int i = estimate.size() - 1; i >= 0 && cmp != 0; --i)
266 if ((cmp = absComp(cur + estimate[i], lhs)) <= 0)
267 cur += estimate[i], ret += powTwo[i];
268 ret.nega = lhs.nega ^ rhs.nega;
269 return ret;
270 }
271 friend BigInt operator/(const BigInt &num,const Long &x){
272 bool negat = ( x < 0 );
273 Long xx = (negat) ? -x : x;
274 BigInt ret;
275 Long k = 0;
276 ret.val.resize( num.size() );
277 ret.nega = (num.nega ^ negat);
278 for(int i = num.size() - 1 ;i >= 0; i--){
279 ret[i] = ( k * Mod + num[i]) / xx;
280 k = ( k * Mod + num[i]) % xx;
281 }
282 ret.trim();
283 return ret;
284 }
285 bool operator==(const BigInt &rhs) const
286 {
287 return nega == rhs.nega && val == rhs.val;
288 }
289 bool operator!=(const BigInt &rhs) const { return nega != rhs.nega || val != rhs.val; }
290 bool operator>=(const BigInt &rhs) const { return !(*this < rhs); }
291 bool operator>(const BigInt &rhs) const { return !(*this <= rhs); }
292 bool operator<=(const BigInt &rhs) const
293 {
294 if (nega && !rhs.nega)
295 return true;
296 if (!nega && rhs.nega)
297 return false;
298 int cmp = absComp(*this, rhs);
299 return nega ? cmp >= 0 : cmp <= 0;
300 }
301 bool operator<(const BigInt &rhs) const
302 {
303 if (nega && !rhs.nega)
304 return true;
305 if (!nega && rhs.nega)
306 return false;
307 return (absComp(*this, rhs) < 0) ^ nega;
308 }
309 void swap(const BigInt &rhs) const
310 {
311 std::swap(val, rhs.val);
312 std::swap(nega, rhs.nega);
313 }
314 };
315 BigInt ba,bb;
316 int main(){
317 cin>>ba>>bb;
318 cout << ba + bb << '\n';//和
319 cout << ba - bb << '\n';//差
320 cout << ba * bb << '\n';//积
321 BigInt d;
322 cout << (d = ba / bb) << '\n';//商
323 cout << ba - d * bb << '\n';//余
324 return 0;
325 }
View Code