#include #include #include #include #include using namespace std; int const logLimit = 3; int const limit = 1 << logLimit; vector rev; void calcRev () { rev = vector (limit, 0); for (int i = 0; i < limit; i++) for (int k = 0; k < logLimit; k++) if (i & (1 << k)) rev[i] ^= 1 << (logLimit - k - 1); } using Num = complex ; double const Pi = acos (-1.0); vector z; void calcZ () { z = vector (limit); for (int i = 0; i < limit; i++) z[i] = Num (cos (i * 2 * Pi / limit), sin (i * 2 * Pi / limit)); } vector fft (const vector & a0, bool inv = false) { vector a = a0; for (int i = 0; i < limit; i++) if (i < rev[i]) swap (a[i], a[rev[i]]); if (inv) reverse (z.begin () + 1, z.end ()); for (int k = 0, span = 1, step = limit / 2; k < logLimit; k++, span *= 2, step /= 2) { for (int i = 0; i < limit; i += 2 * span) for (int j = 0; j < span; j++) { int u = i + j; int v = i + j + span; Num x = a[u] + a[v] * z[j * step]; Num y = a[u] + a[v] * z[j * step + limit / 2]; a[u] = x; a[v] = y; } } if (inv) { reverse (z.begin () + 1, z.end ()); for (int i = 0; i < limit; i++) a[i] /= limit; } return a; } vector readNumber () { string s; cin >> s; vector res (limit, Num (0)); int n = int (s.size ()); for (int i = 0; i < n; i++) res[i] = Num (s[n - 1 - i] - '0'); return res; } int main () { calcRev (); calcZ (); auto a = readNumber (); auto b = readNumber (); auto fa = fft (a); auto fb = fft (b); auto fc = vector (limit); for (int i = 0; i < limit; i++) fc[i] = fa[i] * fb[i]; auto c = fft (fc, true); vector res (limit); long long carry = 0; for (int i = 0; i < limit; i++) { carry += (long long) (c[i].real () + 0.5); res[i] = carry % 10; carry /= 10; } bool started = false; for (int i = limit - 1; i >= 0; i--) { started |= (i == 0) | (res[i] != 0); if (started) cout << res[i]; } cout << endl; return 0; }