Advertisement
Guest User

Untitled

a guest
Dec 16th, 2018
72
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.99 KB | None | 0 0
  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. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement