~~看来只有到 4 月 14 号的志愿者~~
@[Daniel_lele](/user/116664) @[bykem](/user/376161) 申请撤下题解。
by XuYueming @ 2024-04-18 08:28:53
@[ADay](/user/312393)
by _•́へ•́╬_ @ 2024-04-18 09:13:16
@[XuYueming](/user/728079) 虽然他的说法是错的，但是你的其实也是错的。
你不能简单地因为使用了 Python 就认为乘法复杂度 $O(1)$，事实上 Python 计算两个 $n$ 位数乘法复杂度为 $O(n^{\log_2 3})$，总时间复杂度符合 $T(n)=O(n^{\log_2 3})+2T(n/2)$，根据 Master 定理可知这是 $O(n^{\log_2 3})$。
至于其使用的算法，应该是分治算法，还算和二分有点关系。
by yummy @ 2024-04-18 09:21:45
yummy楼下
by _•́へ•́╬_ @ 2024-04-18 09:22:49
@[yummy](/user/101694) 但这不是$n\log n$位数的乘法么
by _•́へ•́╬_ @ 2024-04-18 09:24:54
@[_•́へ•́╬_](/user/90693) 这个取决于假设了，确实，你的假设更加正确（
如果假设是“$n$ 以内的数都能 $O(1)$ 计算”，那么是 $n$ 位数乘法。
如果假设是“对于常数 $B$，$B$ 以内的数都能 $O(1)$ 计算”，那么是 $n(\lfloor \log_B n\rfloor +1)$ 位数乘法。
主要是注意到 OI 中一般 $B>n$，所以我直接用前一种假设简化计算了（
by yummy @ 2024-04-18 09:28:46
~~好吧，其实是我没有考虑到高精乘~~
by XuYueming @ 2024-04-18 09:53:51