Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- const double PI = 3.14;
- 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 = 2 * PI / 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;
- }
- }
- int 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 (size_t i = 0; i < n; ++i)
- fa[i] *= fb[i];
- fft(fa, true);
- res.resize(n);
- for (size_t i = 0; i < n; ++i)
- res[i] = int(fa[i].real() + 0.5);
- int carry = 0;
- for (size_t i = 0; i < n; ++i) {
- res[i] += carry;
- carry = res[i] / 10;
- res[i] %= 10;
- }
- return carry;
- }
- int main() {
- std::string a, b;
- cin >> a >> b;
- vector<int> vect_a, vect_b;
- vect_a.reserve(a.size());
- vect_b.reserve(b.size());
- for (const char &item: a) {
- vect_a.push_back(item);
- }
- for (const char &item: b) {
- vect_b.push_back(item);
- }
- vector<int> res;
- multiply(vect_a, vect_b, res);
- for (const auto &item: res) {
- std::cout << item;
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement