公式

考虑两个多位数a和b, 设其个位分别为a₀和b₀, 十位分别为a₁和b₁ ......

则其乘积可表示为：

a\cdot b=\left(\sum_{i=0}^{m}10^ia_i\right)\cdot\left(\sum_{j=0}^{n}10^ja_j\right)=\sum_{i=0}^{m}\sum_{j=0}^{n}10^{i+j}a_ib_j

(The power of math!)

代码实现

不难将上式写为两个嵌套的for循环

# Code Modified by YRL
def Multply(num1: str, num2: str) -> str:
    num1 = [int(i) for i in num1]
    num2 = [int(i) for i in num2]
    Len1 = len(num1)
    Len2 = len(num2)
    Res = [0] * (Len1 + Len2)
    for i in range(Len1):
        for j in range(Len2):
            Tmp = num1[Len1 - i -1] * num2[Len2 - j -1] + Res[i + j]
            Res[i + j] = Tmp % 10
            Res[i + j + 1] += Tmp // 10
    return ''.join(str(i) for i in Res).rstrip('0')[::-1] or '0'

值得注意的是，公式中的a_k实际对应代码中的\mathrm{num1[Len1 - k - 1]}，写的时候不要出错

复杂度

时间复杂度: O(N*M)

空间复杂度: O(N*M)