Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- //#define getchar getchar_unlocked
- 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 = 2*acos(-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());
- vector<base> 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;
- }
- }
- vector<int> readNumber() {
- deque<int> digits;
- int c = getchar();
- while (c != '-' && !('0' <= c && c <= '9')) {
- c = getchar();
- }
- if (c == '-')
- c = getchar();
- while ('0' <= c && c <= '9')
- digits.push_front(c - '0'), c = getchar();
- return vector<int>(digits.begin(), digits.end());
- }
- int32_t main() {
- ios::sync_with_stdio(false);
- cin.tie(nullptr);
- vector<int> a = readNumber();
- vector<int> b = readNumber();
- vector<int> res;
- multiply(a, b, res);
- bool ok = false;
- for (int i = res.size() - 1; i >= 0; i--) {
- if (!ok && res[i] == 0) {
- continue;
- } else {
- ok = true;
- }
- cout << res[i];
- }
- if (!ok) {
- cout << 0;
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment