Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- typedef complex<double> base;
- void fft (vector<base> &a, bool invert) {
- int n = (int) a.size();
- if (n == 1) return;
- vector<base> a0 (n / 2), a1 (n / 2);
- for (int i = 0, j = 0; i < n; i += 2, ++j) {
- a0[j] = a[i];
- a1[j] = a[i + 1];
- }
- fft (a0, invert);
- fft (a1, invert);
- double ang = 8 * atan2(1, 1) / n * (invert ? -1 : 1);
- base w (1), wn (cos(ang), sin(ang));
- for (int i = 0; i < n / 2; ++i) {
- a[i] = a0[i] + w * a1[i];
- a[i + n / 2] = a0[i] - w * a1[i];
- if (invert)
- a[i] /= 2, a[i + n / 2] /= 2;
- w *= wn;
- }
- }
- void multiply (const vector<int> &a, const vector<int> &b, vector<int> & res) {
- vector<base> fa (a.begin(), a.end()), fb (b.begin(), b.end());
- size_t n = 1;
- while (n < max (a.size(), b.size())) n <<= 1;
- n <<= 1;
- fa.resize (n), fb.resize (n);
- fft (fa, false), fft (fb, false);
- for (int i = 0; i < n; ++i)
- fa[i] *= fb[i];
- fft (fa, true);
- res.resize (n);
- for (int i=0; i < n; ++i)
- res[i] = int (fa[i].real() + 0.5);
- int carry = 0;
- for (int i = 0; i < res.size(); ++i) {
- res[i] += carry;
- carry = res[i] / 10;
- res[i] %= 10;
- }
- }
- int main() {
- string s1, s2;
- cin >> s1 >> s2;
- bool f = true;
- if (s1[0] == '-') {
- f = !f;
- s1.erase(s1.begin());
- }
- if (s2[0] == '-') {
- f = !f;
- s2.erase(s2.begin());
- }
- vector <int> x;
- for (int i = 0; i < s1.length(); ++i) {
- x.push_back((int)s1[i] - (int)'0');
- }
- vector <int> y;
- for (int i = 0; i < s2.length(); ++i) {
- y.push_back((int)s2[i] - (int)'0');
- }
- reverse(x.begin(), x.end());
- reverse(y.begin(), y.end());
- vector <int> ans;
- multiply(x, y, ans);
- while (ans.size() > 1 && ans[ans.size() - 1] == 0) {
- ans.pop_back();
- }
- reverse(ans.begin(), ans.end());
- if (!f && ans[0] != 0)
- cout << '-';
- for (int i = 0; i < ans.size(); i++) {
- cout << ans[i];
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement