rt, FFT做法

from math import *

N = 2097162

r = [0] * N

def change(f, n):
    for i in range(n):
        r[i] = r[i >> 1] >> 1
        if i & 1: r[i] |= n >> 1
    for i in range(n):
        if i < r[i]:
            f[i], f[r[i]] = f[r[i]], f[i]

def FFT(f, n, sign):
    change(f, n)
    i = 2
    while i <= n:
        d = cos(2 * pi / i) + sin(sign * 2 * pi / i) * 1j
        for j in range(0, n, i):
            p = 1
            for k in range(j, j + (i >> 1)):
                a, b = f[k], p * f[k + (i >> 1)]
                f[k], f[k + (i >> 1)] = a + b, a - b
                p *= d
        i <<= 1
    if sign == -1:
        for i in range(n):
            f[i] /= n

a, b = input(), input()
x, y = [0] * N, [0] * N
res = [0] * N
c, d = len(a), len(b)
n = 1
while n < max(c, d) << 1: n <<= 1

for i in range(n): x[i], y[i] = (ord(a[c - i - 1]) ^ 48 if i < c else 0), (ord(b[d - i - 1]) ^ 48 if i < d else 0)

FFT(x, n, 1)
FFT(y, n, 1)

for i in range(n): x[i] *= y[i]

FFT(x, n, -1)

for i in range(n): res[i] = int(x[i].real + 0.5)
for i in range(n):
    res[i + 1] += res[i] // 10
    res[i] %= 10

n = c + d - 1
while not res[n] and n: n -= 1

for i in range(n, -1, -1): print(res[i], end='')