代码

#include <complex>
#include <vector>
#include <cstdio>
#include <cstring>
#include <cmath>
using namespace std;
#define complex complex<double>
#define polynomial vector<complex>
const int maxn = 10009;
const int maxm = 16389;
const double PI = acos(-1.0);
char A[maxn], B[maxn], *ca = A + 5, *cb = B + 5;
int a[maxm], b[maxm], c[maxm], n, m, n2, m2;
polynomial va, vb;
int rev[maxm];
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] / 100, c[i] %= 100;
	return n + m + int(bool(c[n + m + 1]));
}
inline void put_2int(int x) {
	if (x <= 9) putchar('0' + x);
	else putchar('0' + (x / 10)), putchar('0' + (x % 10));
}
inline void put_int(int x) {
	putchar('0' + (x / 10)), putchar('0' + (x % 10));
}
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 -= 2) a[n2++] = 10 * (ca[i - 1] - '0') + (ca[i] - '0');
	for (int i = m - 1; i >= 0; i -= 2) b[m2++] = 10 * (cb[i - 1] - '0') + (cb[i] - '0');
	int x = poly_multiply(a, n2 - 1, b, m2 - 1, c);
	while (c[x] == 0 && x) --x;
	put_2int(c[x]);
	for (int i = x - 1; i >= 0; --i) put_int(c[i]);
	putchar('\n');
	return 0;
}

评测结果