代码

#include <bits/stdc++.h>
using namespace std;
#define complex complex<double>
#define polynomial vector<complex>
const int maxn = 2100005;
const double PI = 3.14159265358979323846;
char A[maxn], B[maxn], *ca = A + 5, *cb = B + 5;
int a[maxn], b[maxn], c[maxn], n, m, n2, m2;
polynomial va, vb;
int rev[maxn];
void DFT(polynomial &a, bool inv) {
	int n = a.size();
	for (int i = 0; i < n; ++i) if (rev[i] < i) swap(a[i], a[rev[i]]);
	double pi = inv ? -PI : PI;
	for (int step = 1; step < n; step <<= 1) {
		double theta = pi / step;
		for (int k = 0; k < step; ++k) {
			complex omega_k = exp(complex(0, theta * k));
			for (int ek = k; ek < n; ek += step << 1) {
				int ok = ek + step;
				complex t = a[ok] * omega_k;
				a[ok] = a[ek] - t;
				a[ek] += t;
			}
		}
	}
	if (inv) for (int i = 0; i < n; ++i) a[i] /= n;
}
int poly_multiply(int *a, int n, int *b, int m, int *c) {
	int t, bit;
	for (t = 2, bit = 1; t < n + m + 2; t <<= 1, ++bit);
	rev[0] = 0;
	for (int i = 1; i < t; ++i) {
		rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << (bit - 1));
	}
	va.resize(t, 0);
	vb.resize(t, 0);
	for (int i = 0; i <= n; ++i) va[i] = a[i];
	for (int i = 0; i <= m; ++i) vb[i] = b[i];
	DFT(va, false);
	DFT(vb, false);
	for (int i = 0; i < t; ++i) va[i] *= vb[i];
	DFT(va, true);
	for (int i = 0; i <= n + m; ++i) c[i] = int(va[i].real() + 0.5);
	for (int i = 0; i <= n + m; ++i) c[i + 1] += c[i] / 10000, c[i] %= 10000;
	return n + m + int(bool(c[n + m + 1]));
}
int main() {
	scanf("%s%s", ca, cb);
	n = strlen(ca), m = strlen(cb);
	A[0] = A[1] = A[2] = A[3] = A[4] = B[0] = B[1] = B[2] = B[3] = B[4] = '0';
	n2 = m2 = 0;
	for (int i = n - 1; i >= 0; i -= 4) a[n2++] = 1000 * (ca[i - 3] - '0') + 100 * (ca[i - 2] - '0') + 10 * (ca[i - 1] - '0') + ca[i] - '0';
	for (int i = n - 1; i >= 0; i -= 4) b[m2++] = 1000 * (cb[i - 3] - '0') + 100 * (cb[i - 2] - '0') + 10 * (cb[i - 1] - '0') + cb[i] - '0';
	int x = poly_multiply(a, n2, b, m2, c);
	while (c[x] == 0 && x) --x;
	printf("%d", c[x]);
	for (int i = x - 1; ~i; --i) printf("%04d", c[i]);
	putchar('\n');
	return 0;
}

评测结果