Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <vector>
- #include <complex>
- #include <iostream>
- #include <math.h>
- #include <algorithm>
- //#include <bits/stdc++.h>
- #define fori(a) for(int i = 0; i < a; i++)
- #define forj(b) for(int j = 0; j < b; j++)
- #define forf(b) for(int f = 0; f < b; f++)
- #define forii(a, b) for(int i = a; i < b; i++)
- #define forjj(a, b) for(int j = a; j < b; j++)
- #define elif else if
- #define ll long long
- using namespace std;
- void fast_fourier_forward(vector<complex<double>> & a) {
- int n = a.size();
- if (n == 1) {
- return;
- }
- vector<complex<double>> f(n/2), s(n/2);
- int j = 0;
- for (int i = 0; i < n; i += 2) {
- f[j] = a[i];
- s[j] = a[i+1];
- ++j;
- }
- fast_fourier_forward(f);
- fast_fourier_forward(s);
- double alpha = 2*M_PI/n; // бабочковый алгоритм
- complex<double> x(1), x_b(cos(alpha), sin(alpha));
- for (int i = 0; i < n/2; ++i) {
- a[i] = f[i] + x*s[i];
- a[i+n/2] = f[i] - x*s[i];
- x *= x_b;
- }
- }
- void fast_fourier_invert(vector<complex<double>> & a) {
- int n = a.size();
- if (n == 1) {
- return;
- }
- vector<complex<double>> f(n/2), s(n/2);
- int j = 0;
- for (int i = 0; i < n; i += 2) {
- f[j] = a[i];
- s[j] = a[i+1];
- ++j;
- }
- fast_fourier_invert(f);
- fast_fourier_invert(s);
- double alpha = -2*M_PI/n;
- complex<double> x(1), x_b(cos(alpha), sin(alpha));
- for (int i = 0; i < n/2; ++i) {
- a[i] = f[i] + x*s[i];
- a[i+n/2] = f[i] - x*s[i];
- a[i] /= 2;
- a[i+n/2] /= 2;
- x *= x_b;
- }
- }
- void mult(vector<int> & a, vector<int> & b, vector<int> & res) {
- vector<complex<double>> a_f(a.begin(), a.end()), b_f(b.begin(), b.end());
- int n = 1;
- while (n < a.size() || n < b.size()) {
- n *= 2;
- }
- n *= 2;
- a_f.resize(n);
- b_f.resize(n);
- fast_fourier_forward(a_f);
- fast_fourier_forward(b_f);
- for (int i = 0; i < n; ++i) {
- a_f[i] *= b_f[i];
- }
- fast_fourier_invert(a_f);
- res.resize(n);
- for (int i = 0; i < n; ++i) {
- res[i] = int(a_f[i].real() + 0.5);
- }
- }
- int main() {
- string a, b;
- cin >> a >> b;
- if (a == "0" || b == "0") {
- cout <<'0';
- return 0;
- }
- int sign = 1;
- vector<int> v_a, v_b, res;
- if (a[0] == '-') {
- sign *= -1;
- v_a.resize(a.size()-1);
- for (int i = 0; i < v_a.size(); ++i) {
- v_a[i] = a[i+1] - '0';
- }
- } else {
- v_a.resize(a.size());
- for (int i = 0; i < v_a.size(); ++i) {
- v_a[i] = a[i] - '0';
- }
- }
- if (b[0] == '-') {
- sign *= -1;
- v_b.resize(b.size()-1);
- for (int i = 0; i < v_b.size(); ++i) {
- v_b[i] = b[i+1] - '0';
- }
- } else {
- v_b.resize(b.size());
- for (int i = 0; i < v_b.size(); ++i) {
- v_b[i] = b[i] - '0';
- }
- }
- // cout << "Making polynom from number:";
- // forii(0, v_a.size()) {
- // cout << v_a[i] << " ";
- // }
- // cout << endl;
- // double n = 5;
- // double alpha = 2*M_PI/n;
- // complex<double> x_bb(cos(alpha), sin(alpha));
- // cout << x_bb;
- reverse(v_a.begin(), v_a.end());
- reverse(v_b.begin(), v_b.end());
- mult(v_a, v_b, res);
- int saved = 0, c = 0;
- for (int & re : res) {
- re += saved;
- saved = re / 10;
- re %= 10;
- }
- reverse(res.begin(), res.end());
- bool fl = false;
- if (sign == -1) {
- cout<<'-';
- }
- for (int & re : res) {
- if (!fl) {
- if (re != 0) {
- fl = true;
- }
- }
- if (fl) {
- cout << re;
- }
- }
- }
Add Comment
Please, Sign In to add comment