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
| struct bigint
{
bool neg;
vector<short> num;
bigint() { neg = 0; }
bigint(vector<short> vec){ neg = 0; num = vec;}
bigint(vector<long long> vec){ for(auto i:vec) num.push_back(i); neg = 0;}
bigint(int x) { if(x < 0) neg = 1, x = -x; while(x) num.push_back(x % 10), x /= 10; }
bigint(long long x) { if(x < 0) neg = 1, x = -x; while(x) num.push_back(x % 10), x /= 10; }
bigint(string str) { if(str[0]=='-') neg = 1, str.erase(str.begin()); else neg = 0; for (int i = (int)str.size() - 1; i >= 0; i--) num.push_back(str[i] - '0'); (*this).clearz(); }
void fill(int pos, int val){ while((int)num.size() <= pos) num.push_back(0); num[pos] = val; }
void add(int pos, int val) { while((int)num.size() <= pos) num.push_back(0); num[pos] += val; }
void clearz() { while(!num.empty() && num.back() == 0) num.pop_back(); }
void operator=(int x) { *this = bigint(x);}
void operator=(long long x) { *this = bigint(x);}
bool operator==(bigint b) { bigint a = *this; return a.neg == b.neg && a.num == b.num; }
bool operator<(bigint b) { bigint a = *this; return a.neg != b.neg ? (a.neg && !b.neg) : (a.num.size() != b.num.size() ? (a.neg ? a.num.size() > b.num.size() : a.num.size() < b.num.size()) : (a.neg ? a.num > b.num : a.num < b.num)); }
bool operator>(bigint b) { bigint a = *this; return !(a < b || a == b); }
bool operator!=(bigint b) { bigint a = *this; return !(a == b); }
bool operator<=(bigint b) { bigint a = *this; return a < b || a == b; }
bool operator>=(bigint b) { bigint a = *this; return a > b || a == b; }
friend istream &operator>>(istream &is, bigint &p) { string str; is >> str; p = bigint(str); return is; }
friend ostream &operator<<(ostream &os, const bigint &p) { if(p.neg) os << "-"; for (int i = p.num.size() - 1; i >= 0; i--) os << p.num[i]; if(p.num.empty()) os << 0; return os; }
bigint operator+(bigint b)
{
bigint res;
bigint a = *this;
if(a.neg && b.neg) res.neg = 1;
else if (a.neg){ a.neg = 0; return b - a;}
else if (b.neg){ b.neg = 0; return a - b;}
vector<short> x = a.num, y = b.num;
if(x.size() > y.size()) swap(x, y);
while(x.size() != y.size()) x.push_back(0);
for (int i = 0; i < (int)x.size(); i++)
{
res.add(i, x[i] + y[i]);
if(res.num[i] >= 10)
res.add(i + 1, 1), res.num[i] -= 10;
}
res.clearz();
return res;
}
bigint operator-(bigint b)
{
bigint res;
bigint a = *this;
if (a.neg && b.neg) a.neg = b.neg = 0, swap(a, b);
else if(a.neg){ b.neg = 1; return a + b;}
else if(b.neg){ b.neg = 0; return a + b;}
if (a < b) swap(a, b), res.neg = 1;
while (a.num.size() != b.num.size()) b.num.push_back(0);
vector<short> x = a.num, y = b.num;
for (int i = 0; i < (int)x.size(); i++)
{
res.add(i, x[i] - y[i]);
if(res.num[i] < 0) res.add(i + 1, -1), res.num[i] += 10;
}
res.clearz();
return res;
}
void FFT(int k, complex<double> *a, int t)
{
if (k <= 1) return;
int mid = k >> 1;
complex<double> a1[mid], a2[mid];
for (int i = 0; i < mid; i++) a1[i] = a[i * 2], a2[i] = a[i * 2 + 1];
FFT(mid, a1, t), FFT(mid, a2, t);
complex<double> x(cos(acos(-1.0) / mid), t * sin(acos(-1.0) / mid)), y(1, 0);
for (int i = 0; i < mid; i++) { complex<double> xx = y * a2[i]; a[i] = a1[i] + xx; a[i + mid] = a1[i] - xx; y *= x; }
}
bigint operator *(bigint b)
{
int k = 1;
while (k <= (int)num.size() + (int)b.num.size() - 2) k *= 2;
complex<double> x[k], y[k], ans[k];
for (int i = 0; i < num.size(); i++) x[i] = complex<double>(num[i], 0);
for (int i = 0; i < b.num.size(); i++) y[i] = complex<double>(b.num[i], 0);
FFT(k, x, 1), FFT(k, y, 1);
for (int i = 0; i < k; i++) ans[i] = x[i] * y[i];
FFT(k, ans, -1);
vector<long long> nw;
for (int i = 0; i < k; i++) nw.push_back(round(ans[i].real() / k));
for (int i = 0; i < nw.size(); i++) if (nw[i] >= 10) { if (i == nw.size() - 1) nw.push_back(0); nw[i + 1] += nw[i] / 10; nw[i] %= 10;}
bigint res(nw);
res.clearz();
res.neg = neg ^ b.neg;
return res;
}
void operator +=(bigint b) { *this = *this + b; }
void operator -=(bigint b) { *this = *this - b; }
void operator *=(bigint b) { *this = *this * b; }
};
|