Advertisement
Art_Uspen

Untitled

Oct 15th, 2021
839
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.70 KB | None | 0 0
  1. const double PI = 3.14;
  2. typedef complex<double> base;
  3.  
  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 = 2 * PI / 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. int 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.  
  34.     fft(fa, false), fft(fb, false);
  35.     for (size_t i = 0; i < n; ++i)
  36.         fa[i] *= fb[i];
  37.     fft(fa, true);
  38.  
  39.     res.resize(n);
  40.     for (size_t i = 0; i < n; ++i)
  41.         res[i] = int(fa[i].real() + 0.5);
  42.     int carry = 0;
  43.     for (size_t i = 0; i < n; ++i) {
  44.         res[i] += carry;
  45.         carry = res[i] / 10;
  46.         res[i] %= 10;
  47.     }
  48.     return carry;
  49. }
  50.  
  51. int main() {
  52.     std::string a, b;
  53.     cin >> a >> b;
  54.     vector<int> vect_a, vect_b;
  55.     vect_a.reserve(a.size());
  56.     vect_b.reserve(b.size());
  57.     for (const char &item: a) {
  58.         vect_a.push_back(item);
  59.     }
  60.     for (const char &item: b) {
  61.         vect_b.push_back(item);
  62.     }
  63.     vector<int> res;
  64.     multiply(vect_a, vect_b, res);
  65.     for (const auto &item: res) {
  66.         std::cout << item;
  67.     }
  68.     return 0;
  69. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement