1224 - 奶牛乘法
时间: 2023-06-27 21:06:52 浏览: 69
题目描述:
给定两个 $N$ 位数 $A$ 和 $B$,求 $A \times B$ 的值。
$N \leq 50000$,时限 $\texttt{3s}$,空间限制:$128\texttt{MB}$。
输入格式
共两行,每行一个字符串表示一个数,字符串长度不超过 $50000$。
输出格式
共一行,表示 $A \times B$ 的值。
样例输入
12345678901234567890
98765432109876543210
样例输出
1219326311370217950438555261352247308900
算法1
(分治) $O(n\log n)$
同类题目:P1906 大整数乘法
思路:
使用分治的思想,将两个大整数均分成两个部分。
设 $a_1,a_2$ 分别为 $A$ 的左右两半,$b_1,b_2$ 分别为 $B$ 的左右两半。则有
$$A\times B = (a_1\times 10^{\frac{n}{2}}+a_2)\times (b_1\times 10^{\frac{n}{2}}+b_2)$$
展开后可得:
$$A\times B = a_1\times b_1\times 10^n+(a_1\times b_2+a_2\times b_1)\times 10^{\frac{n}{2}}+a_2\times b_2$$
可以发现,计算 $a_1\times b_1$、$a_1\times b_2$、$a_2\times b_1$、$a_2\times b_2$ 四个数的乘积即可得到 $A\times B$ 的值。
时间复杂度分析:设 $T(n)$ 表示计算 $n$ 位数积的时间复杂度,则有:
$$T(n)=4T\left(\frac{n}{2}\right)+O(n)$$
通过 master 定理可以得到 $T(n)=O(n\log n)$。
C++ 代码