• API
• FAQ
• Tools
• Archive
daily pastebin goal
58%
SHARE
TWEET

# Untitled

a guest Dec 16th, 2018 53 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1. #include <bits/stdc++.h>
2. using namespace std;
3. typedef complex<double> base;
4. void fft (vector<base> &a, bool invert) {
5.     int n = (int) a.size();
6.     if (n == 1)  return;
7.
8.     vector<base> a0 (n / 2),  a1 (n / 2);
9.     for (int i = 0, j = 0; i < n; i += 2, ++j) {
10.         a0[j] = a[i];
11.         a1[j] = a[i + 1];
12.     }
13.     fft (a0, invert);
14.     fft (a1, invert);
15.
16.     double ang = 8 * atan2(1, 1) / n * (invert ? -1 : 1);
17.     base w (1),  wn (cos(ang), sin(ang));
18.     for (int i = 0; i < n / 2; ++i) {
19.         a[i] = a0[i] + w * a1[i];
20.         a[i + n / 2] = a0[i] - w * a1[i];
21.         if (invert)
22.             a[i] /= 2,  a[i + n / 2] /= 2;
23.         w *= wn;
24.     }
25. }
26.
27. void multiply (const vector<int> &a, const vector<int> &b, vector<int> & res) {
28.     vector<base> fa (a.begin(), a.end()),  fb (b.begin(), b.end());
29.     size_t n = 1;
30.     while (n < max (a.size(), b.size()))  n <<= 1;
31.     n <<= 1;
32.     fa.resize (n),  fb.resize (n);
33.     fft (fa, false),  fft (fb, false);
34.     for (int i = 0; i < n; ++i)
35.         fa[i] *= fb[i];
36.     fft (fa, true);
37.     res.resize (n);
38.     for (int i=0; i < n; ++i)
39.         res[i] = int (fa[i].real() + 0.5);
40.     int carry = 0;
41.     for (int i = 0; i < res.size(); ++i) {
42.         res[i] += carry;
43.         carry = res[i] / 10;
44.         res[i] %= 10;
45.     }
46. }
47.
48. int main() {
49.     string s1, s2;
50.     cin >> s1 >> s2;
51.     bool f = true;
52.     if (s1[0] == '-') {
53.         f = !f;
54.         s1.erase(s1.begin());
55.     }
56.     if (s2[0] == '-') {
57.         f = !f;
58.         s2.erase(s2.begin());
59.     }
60.     vector <int> x;
61.     for (int i = 0; i < s1.length(); ++i) {
62.         x.push_back((int)s1[i] - (int)'0');
63.     }
64.     vector <int> y;
65.     for (int i = 0; i < s2.length(); ++i) {
66.         y.push_back((int)s2[i] - (int)'0');
67.     }
68.     reverse(x.begin(), x.end());
69.     reverse(y.begin(), y.end());
70.     vector <int> ans;
71.     multiply(x, y, ans);
72.     while (ans.size() > 1 && ans[ans.size() - 1] == 0) {
73.         ans.pop_back();
74.     }
75.     reverse(ans.begin(), ans.end());
76.     if (!f && ans[0] != 0)
77.         cout << '-';
78.     for (int i = 0; i < ans.size(); i++) {
79.         cout << ans[i];
80.     }
81. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.

Top